fs/fat/cache.c

   1 /*
   2  *  linux/fs/fat/cache.c
   3  *
   4  *  Written 1992,1993 by Werner Almesberger
   5  *
   6  *  Mar 1999. AV. Changed cache, so that it uses the starting cluster instead
   7  *      of inode number.
   8  *  May 1999. AV. Fixed the bogosity with FAT32 (read "FAT28"). Fscking lusers.
   9  */
  10
  11 #include <linux/fs.h>
  12 #include <linux/msdos_fs.h>
  13 #include <linux/buffer_head.h>
  14
  15 /* this must be > 0. */
  16 #define FAT_MAX_CACHE   8
  17
  18 struct fat_cache {
  19         struct list_head cache_list;
  20         int nr_contig;  /* number of contiguous clusters */
  21         int fcluster;   /* cluster number in the file. */
  22         int dcluster;   /* cluster number on disk. */
  23 };
  24
  25 struct fat_cache_id {
  26         unsigned int id;
  27         int nr_contig;
  28         int fcluster;
  29         int dcluster;
  30 };
  31
  32 static inline int fat_max_cache(struct inode *inode)
  33 {
  34         return FAT_MAX_CACHE;
  35 }
  36
  37 static kmem_cache_t *fat_cache_cachep;
  38
  39 static void init_once(void *foo, kmem_cache_t *cachep, unsigned long flags)
  40 {
  41         struct fat_cache *cache = (struct fat_cache *)foo;
  42
  43         if ((flags & (SLAB_CTOR_VERIFY|SLAB_CTOR_CONSTRUCTOR)) ==
  44             SLAB_CTOR_CONSTRUCTOR)
  45                 INIT_LIST_HEAD(&cache->cache_list);
  46 }
  47
  48 int __init fat_cache_init(void)
  49 {
  50         fat_cache_cachep = kmem_cache_create("fat_cache",
  51                                 sizeof(struct fat_cache),
  52                                 0, SLAB_RECLAIM_ACCOUNT,
  53                                 init_once, NULL);
  54         if (fat_cache_cachep == NULL)
  55                 return -ENOMEM;
  56         return 0;
  57 }
  58
  59 void __exit fat_cache_destroy(void)
  60 {
  61         if (kmem_cache_destroy(fat_cache_cachep))
  62                 printk(KERN_INFO "fat_cache: not all structures were freed\n");
  63 }
  64
  65 static inline struct fat_cache *fat_cache_alloc(struct inode *inode)
  66 {
  67         return kmem_cache_alloc(fat_cache_cachep, SLAB_KERNEL);
  68 }
  69
  70 static inline void fat_cache_free(struct fat_cache *cache)
  71 {
  72         BUG_ON(!list_empty(&cache->cache_list));
  73         kmem_cache_free(fat_cache_cachep, cache);
  74 }
  75
  76 static inline void fat_cache_update_lru(struct inode *inode,
  77                                         struct fat_cache *cache)
  78 {
  79         if (MSDOS_I(inode)->cache_lru.next != &cache->cache_list)
  80                 list_move(&cache->cache_list, &MSDOS_I(inode)->cache_lru);
  81 }
  82
  83 static int fat_cache_lookup(struct inode *inode, int fclus,
  84                             struct fat_cache_id *cid,
  85                             int *cached_fclus, int *cached_dclus)
  86 {
  87         static struct fat_cache nohit = { .fcluster = 0, };
  88
  89         struct fat_cache *hit = &nohit, *p;
  90         int offset = -1;
  91
  92         spin_lock(&MSDOS_I(inode)->cache_lru_lock);
  93         list_for_each_entry(p, &MSDOS_I(inode)->cache_lru, cache_list) {
  94                 /* Find the cache of "fclus" or nearest cache. */
  95                 if (p->fcluster <= fclus && hit->fcluster < p->fcluster) {
  96                         hit = p;
  97                         if ((hit->fcluster + hit->nr_contig) < fclus) {
  98                                 offset = hit->nr_contig;
  99                         } else {
 100                                 offset = fclus - hit->fcluster;
 101                                 break;
 102                         }
 103                 }
 104         }
 105         if (hit != &nohit) {
 106                 fat_cache_update_lru(inode, hit);
 107
 108                 cid->id = MSDOS_I(inode)->cache_valid_id;
 109                 cid->nr_contig = hit->nr_contig;
 110                 cid->fcluster = hit->fcluster;
 111                 cid->dcluster = hit->dcluster;
 112                 *cached_fclus = cid->fcluster + offset;
 113                 *cached_dclus = cid->dcluster + offset;
 114         }
 115         spin_unlock(&MSDOS_I(inode)->cache_lru_lock);
 116
 117         return offset;
 118 }
 119
 120 static struct fat_cache *fat_cache_merge(struct inode *inode,
 121                                          struct fat_cache_id *new)
 122 {
 123         struct fat_cache *p;
 124
 125         list_for_each_entry(p, &MSDOS_I(inode)->cache_lru, cache_list) {
 126                 /* Find the same part as "new" in cluster-chain. */
 127                 if (p->fcluster == new->fcluster) {
 128                         BUG_ON(p->dcluster != new->dcluster);
 129                         if (new->nr_contig > p->nr_contig)
 130                                 p->nr_contig = new->nr_contig;
 131                         return p;
 132                 }
 133         }
 134         return NULL;
 135 }
 136
 137 static void fat_cache_add(struct inode *inode, struct fat_cache_id *new)
 138 {
 139         struct fat_cache *cache, *tmp;
 140
 141         if (new->fcluster == -1) /* dummy cache */
 142                 return;
 143
 144         spin_lock(&MSDOS_I(inode)->cache_lru_lock);
 145         if (new->id != FAT_CACHE_VALID &&
 146             new->id != MSDOS_I(inode)->cache_valid_id)
 147                 goto out;       /* this cache was invalidated */
 148
 149         cache = fat_cache_merge(inode, new);
 150         if (cache == NULL) {
 151                 if (MSDOS_I(inode)->nr_caches < fat_max_cache(inode)) {
 152                         MSDOS_I(inode)->nr_caches++;
 153                         spin_unlock(&MSDOS_I(inode)->cache_lru_lock);
 154
 155                         tmp = fat_cache_alloc(inode);
 156                         spin_lock(&MSDOS_I(inode)->cache_lru_lock);
 157                         cache = fat_cache_merge(inode, new);
 158                         if (cache != NULL) {
 159                                 MSDOS_I(inode)->nr_caches--;
 160                                 fat_cache_free(tmp);
 161                                 goto out_update_lru;
 162                         }
 163                         cache = tmp;
 164                 } else {
 165                         struct list_head *p = MSDOS_I(inode)->cache_lru.prev;
 166                         cache = list_entry(p, struct fat_cache, cache_list);
 167                 }
 168                 cache->fcluster = new->fcluster;
 169                 cache->dcluster = new->dcluster;
 170                 cache->nr_contig = new->nr_contig;
 171         }
 172 out_update_lru:
 173         fat_cache_update_lru(inode, cache);
 174 out:
 175         spin_unlock(&MSDOS_I(inode)->cache_lru_lock);
 176 }
 177
 178 /*
 179  * Cache invalidation occurs rarely, thus the LRU chain is not updated. It
 180  * fixes itself after a while.
 181  */
 182 static void __fat_cache_inval_inode(struct inode *inode)
 183 {
 184         struct msdos_inode_info *i = MSDOS_I(inode);
 185         struct fat_cache *cache;
 186
 187         while (!list_empty(&i->cache_lru)) {
 188                 cache = list_entry(i->cache_lru.next, struct fat_cache, cache_list);
 189                 list_del_init(&cache->cache_list);
 190                 i->nr_caches--;
 191                 fat_cache_free(cache);
 192         }
 193         /* Update. The copy of caches before this id is discarded. */
 194         i->cache_valid_id++;
 195         if (i->cache_valid_id == FAT_CACHE_VALID)
 196                 i->cache_valid_id++;
 197 }
 198
 199 void fat_cache_inval_inode(struct inode *inode)
 200 {
 201         spin_lock(&MSDOS_I(inode)->cache_lru_lock);
 202         __fat_cache_inval_inode(inode);
 203         spin_unlock(&MSDOS_I(inode)->cache_lru_lock);
 204 }
 205
 206 static int __fat_access(struct super_block *sb, int nr, int new_value)
 207 {
 208         struct msdos_sb_info *sbi = MSDOS_SB(sb);
 209         struct buffer_head *bh, *bh2, *c_bh, *c_bh2;
 210         unsigned char *p_first, *p_last;
 211         int copy, first, last, next, b;
 212
 213         if (sbi->fat_bits == 32) {
 214                 first = last = nr*4;
 215         } else if (sbi->fat_bits == 16) {
 216                 first = last = nr*2;
 217         } else {
 218                 first = nr*3/2;
 219                 last = first+1;
 220         }
 221         b = sbi->fat_start + (first >> sb->s_blocksize_bits);
 222         if (!(bh = sb_bread(sb, b))) {
 223                 printk(KERN_ERR "FAT: bread(block %d) in"
 224                        " fat_access failed\n", b);
 225                 return -EIO;
 226         }
 227         if ((first >> sb->s_blocksize_bits) == (last >> sb->s_blocksize_bits)) {
 228                 bh2 = bh;
 229         } else {
 230                 if (!(bh2 = sb_bread(sb, b + 1))) {
 231                         brelse(bh);
 232                         printk(KERN_ERR "FAT: bread(block %d) in"
 233                                " fat_access failed\n", b + 1);
 234                         return -EIO;
 235                 }
 236         }
 237         if (sbi->fat_bits == 32) {
 238                 p_first = p_last = NULL; /* GCC needs that stuff */
 239                 next = le32_to_cpu(((__le32 *) bh->b_data)[(first &
 240                     (sb->s_blocksize - 1)) >> 2]);
 241                 /* Fscking Microsoft marketing department. Their "32" is 28. */
 242                 next &= 0x0fffffff;
 243         } else if (sbi->fat_bits == 16) {
 244                 p_first = p_last = NULL; /* GCC needs that stuff */
 245                 next = le16_to_cpu(((__le16 *) bh->b_data)[(first &
 246                     (sb->s_blocksize - 1)) >> 1]);
 247         } else {
 248                 p_first = &((__u8 *)bh->b_data)[first & (sb->s_blocksize - 1)];
 249                 p_last = &((__u8 *)bh2->b_data)[(first + 1) & (sb->s_blocksize - 1)];
 250                 if (nr & 1)
 251                         next = ((*p_first >> 4) | (*p_last << 4)) & 0xfff;
 252                 else
 253                         next = (*p_first+(*p_last << 8)) & 0xfff;
 254         }
 255         if (new_value != -1) {
 256                 if (sbi->fat_bits == 32) {
 257                         ((__le32 *)bh->b_data)[(first & (sb->s_blocksize - 1)) >> 2]
 258                                 = cpu_to_le32(new_value);
 259                 } else if (sbi->fat_bits == 16) {
 260                         ((__le16 *)bh->b_data)[(first & (sb->s_blocksize - 1)) >> 1]
 261                                 = cpu_to_le16(new_value);
 262                 } else {
 263                         if (nr & 1) {
 264                                 *p_first = (*p_first & 0xf) | (new_value << 4);
 265                                 *p_last = new_value >> 4;
 266                         }
 267                         else {
 268                                 *p_first = new_value & 0xff;
 269                                 *p_last = (*p_last & 0xf0) | (new_value >> 8);
 270                         }
 271                         mark_buffer_dirty(bh2);
 272                 }
 273                 mark_buffer_dirty(bh);
 274                 for (copy = 1; copy < sbi->fats; copy++) {
 275                         b = sbi->fat_start + (first >> sb->s_blocksize_bits)
 276                                 + sbi->fat_length * copy;
 277                         if (!(c_bh = sb_bread(sb, b)))
 278                                 break;
 279                         if (bh != bh2) {
 280                                 if (!(c_bh2 = sb_bread(sb, b+1))) {
 281                                         brelse(c_bh);
 282                                         break;
 283                                 }
 284                                 memcpy(c_bh2->b_data, bh2->b_data, sb->s_blocksize);
 285                                 mark_buffer_dirty(c_bh2);
 286                                 brelse(c_bh2);
 287                         }
 288                         memcpy(c_bh->b_data, bh->b_data, sb->s_blocksize);
 289                         mark_buffer_dirty(c_bh);
 290                         brelse(c_bh);
 291                 }
 292         }
 293         brelse(bh);
 294         if (bh != bh2)
 295                 brelse(bh2);
 296         return next;
 297 }
 298
 299 /*
 300  * Returns the this'th FAT entry, -1 if it is an end-of-file entry. If
 301  * new_value is != -1, that FAT entry is replaced by it.
 302  */
 303 int fat_access(struct super_block *sb, int nr, int new_value)
 304 {
 305         int next;
 306
 307         next = -EIO;
 308         if (nr < FAT_START_ENT || MSDOS_SB(sb)->max_cluster <= nr) {
 309                 fat_fs_panic(sb, "invalid access to FAT (entry 0x%08x)", nr);
 310                 goto out;
 311         }
 312         if (new_value == FAT_ENT_EOF)
 313                 new_value = EOF_FAT(sb);
 314
 315         next = __fat_access(sb, nr, new_value);
 316         if (next < 0)
 317                 goto out;
 318         if (next >= BAD_FAT(sb))
 319                 next = FAT_ENT_EOF;
 320 out:
 321         return next;
 322 }
 323
 324 static inline int cache_contiguous(struct fat_cache_id *cid, int dclus)
 325 {
 326         cid->nr_contig++;
 327         return ((cid->dcluster + cid->nr_contig) == dclus);
 328 }
 329
 330 static inline void cache_init(struct fat_cache_id *cid, int fclus, int dclus)
 331 {
 332         cid->id = FAT_CACHE_VALID;
 333         cid->fcluster = fclus;
 334         cid->dcluster = dclus;
 335         cid->nr_contig = 0;
 336 }
 337
 338 int fat_get_cluster(struct inode *inode, int cluster, int *fclus, int *dclus)
 339 {
 340         struct super_block *sb = inode->i_sb;
 341         const int limit = sb->s_maxbytes >> MSDOS_SB(sb)->cluster_bits;
 342         struct fat_cache_id cid;
 343         int nr;
 344
 345         BUG_ON(MSDOS_I(inode)->i_start == 0);
 346
 347         *fclus = 0;
 348         *dclus = MSDOS_I(inode)->i_start;
 349         if (cluster == 0)
 350                 return 0;
 351
 352         if (fat_cache_lookup(inode, cluster, &cid, fclus, dclus) < 0) {
 353                 /*
 354                  * dummy, always not contiguous
 355                  * This is reinitialized by cache_init(), later.
 356                  */
 357                 cache_init(&cid, -1, -1);
 358         }
 359
 360         while (*fclus < cluster) {
 361                 /* prevent the infinite loop of cluster chain */
 362                 if (*fclus > limit) {
 363                         fat_fs_panic(sb, "%s: detected the cluster chain loop"
 364                                      " (i_pos %lld)", __FUNCTION__,
 365                                      MSDOS_I(inode)->i_pos);
 366                         return -EIO;
 367                 }
 368
 369                 nr = fat_access(sb, *dclus, -1);
 370                 if (nr < 0)
 371                         return nr;
 372                 else if (nr == FAT_ENT_FREE) {
 373                         fat_fs_panic(sb, "%s: invalid cluster chain"
 374                                      " (i_pos %lld)", __FUNCTION__,
 375                                      MSDOS_I(inode)->i_pos);
 376                         return -EIO;
 377                 } else if (nr == FAT_ENT_EOF) {
 378                         fat_cache_add(inode, &cid);
 379                         return FAT_ENT_EOF;
 380                 }
 381                 (*fclus)++;
 382                 *dclus = nr;
 383                 if (!cache_contiguous(&cid, *dclus))
 384                         cache_init(&cid, *fclus, *dclus);
 385         }
 386         fat_cache_add(inode, &cid);
 387         return 0;
 388 }
 389
 390 static int fat_bmap_cluster(struct inode *inode, int cluster)
 391 {
 392         struct super_block *sb = inode->i_sb;
 393         int ret, fclus, dclus;
 394
 395         if (MSDOS_I(inode)->i_start == 0)
 396                 return 0;
 397
 398         ret = fat_get_cluster(inode, cluster, &fclus, &dclus);
 399         if (ret < 0)
 400                 return ret;
 401         else if (ret == FAT_ENT_EOF) {
 402                 fat_fs_panic(sb, "%s: request beyond EOF (i_pos %lld)",
 403                              __FUNCTION__, MSDOS_I(inode)->i_pos);
 404                 return -EIO;
 405         }
 406         return dclus;
 407 }
 408
 409 int fat_bmap(struct inode *inode, sector_t sector, sector_t *phys)
 410 {
 411         struct super_block *sb = inode->i_sb;
 412         struct msdos_sb_info *sbi = MSDOS_SB(sb);
 413         sector_t last_block;
 414         int cluster, offset;
 415
 416         *phys = 0;
 417         if ((sbi->fat_bits != 32) &&
 418             (inode->i_ino == MSDOS_ROOT_INO || (S_ISDIR(inode->i_mode) &&
 419              !MSDOS_I(inode)->i_start))) {
 420                 if (sector < (sbi->dir_entries >> sbi->dir_per_block_bits))
 421                         *phys = sector + sbi->dir_start;
 422                 return 0;
 423         }
 424         last_block = (MSDOS_I(inode)->mmu_private + (sb->s_blocksize - 1))
 425                 >> sb->s_blocksize_bits;
 426         if (sector >= last_block)
 427                 return 0;
 428
 429         cluster = sector >> (sbi->cluster_bits - sb->s_blocksize_bits);
 430         offset  = sector & (sbi->sec_per_clus - 1);
 431         cluster = fat_bmap_cluster(inode, cluster);
 432         if (cluster < 0)
 433                 return cluster;
 434         else if (cluster)
 435                 *phys = fat_clus_to_blknr(sbi, cluster) + offset;
 436         return 0;
 437 }