[linux-2.6-block.git] / fs / fat / cache.c

/*
 *  linux/fs/fat/cache.c
 *
 *  Written 1992,1993 by Werner Almesberger
 *
 *  Mar 1999. AV. Changed cache, so that it uses the starting cluster instead
 *	of inode number.
 *  May 1999. AV. Fixed the bogosity with FAT32 (read "FAT28"). Fscking lusers.
 */

#include <linux/fs.h>
#include <linux/buffer_head.h>
#include "fat.h"

/* this must be > 0. */
#define FAT_MAX_CACHE	8

struct fat_cache {
	struct list_head cache_list;
	int nr_contig;	/* number of contiguous clusters */
	int fcluster;	/* cluster number in the file. */
	int dcluster;	/* cluster number on disk. */
};

struct fat_cache_id {
	unsigned int id;
	int nr_contig;
	int fcluster;
	int dcluster;
};

static inline int fat_max_cache(struct inode *inode)
{
	return FAT_MAX_CACHE;
}

static struct kmem_cache *fat_cache_cachep;

static void init_once(void *foo)
{
	struct fat_cache *cache = (struct fat_cache *)foo;

	INIT_LIST_HEAD(&cache->cache_list);
}

int __init fat_cache_init(void)
{
	fat_cache_cachep = kmem_cache_create("fat_cache",
				sizeof(struct fat_cache),
				0, SLAB_RECLAIM_ACCOUNT|SLAB_MEM_SPREAD,
				init_once);
	if (fat_cache_cachep == NULL)
		return -ENOMEM;
	return 0;
}

void fat_cache_destroy(void)
{
	kmem_cache_destroy(fat_cache_cachep);
}

static inline struct fat_cache *fat_cache_alloc(struct inode *inode)
{
	return kmem_cache_alloc(fat_cache_cachep, GFP_NOFS);
}

static inline void fat_cache_free(struct fat_cache *cache)
{
	BUG_ON(!list_empty(&cache->cache_list));
	kmem_cache_free(fat_cache_cachep, cache);
}

static inline void fat_cache_update_lru(struct inode *inode,
					struct fat_cache *cache)
{
	if (MSDOS_I(inode)->cache_lru.next != &cache->cache_list)
		list_move(&cache->cache_list, &MSDOS_I(inode)->cache_lru);
}

static int fat_cache_lookup(struct inode *inode, int fclus,
			    struct fat_cache_id *cid,
			    int *cached_fclus, int *cached_dclus)
{
	static struct fat_cache nohit = { .fcluster = 0, };

	struct fat_cache *hit = &nohit, *p;
	int offset = -1;

	spin_lock(&MSDOS_I(inode)->cache_lru_lock);
	list_for_each_entry(p, &MSDOS_I(inode)->cache_lru, cache_list) {
		/* Find the cache of "fclus" or nearest cache. */
		if (p->fcluster <= fclus && hit->fcluster < p->fcluster) {
			hit = p;
			if ((hit->fcluster + hit->nr_contig) < fclus) {
				offset = hit->nr_contig;
			} else {
				offset = fclus - hit->fcluster;
				break;
			}
		}
	}
	if (hit != &nohit) {
		fat_cache_update_lru(inode, hit);

		cid->id = MSDOS_I(inode)->cache_valid_id;
		cid->nr_contig = hit->nr_contig;
		cid->fcluster = hit->fcluster;
		cid->dcluster = hit->dcluster;
		*cached_fclus = cid->fcluster + offset;
		*cached_dclus = cid->dcluster + offset;
	}
	spin_unlock(&MSDOS_I(inode)->cache_lru_lock);

	return offset;
}

static struct fat_cache *fat_cache_merge(struct inode *inode,
					 struct fat_cache_id *new)
{
	struct fat_cache *p;

	list_for_each_entry(p, &MSDOS_I(inode)->cache_lru, cache_list) {
		/* Find the same part as "new" in cluster-chain. */
		if (p->fcluster == new->fcluster) {
			BUG_ON(p->dcluster != new->dcluster);
			if (new->nr_contig > p->nr_contig)
				p->nr_contig = new->nr_contig;
			return p;
		}
	}
	return NULL;
}

static void fat_cache_add(struct inode *inode, struct fat_cache_id *new)
{
	struct fat_cache *cache, *tmp;

	if (new->fcluster == -1) /* dummy cache */
		return;

	spin_lock(&MSDOS_I(inode)->cache_lru_lock);
	if (new->id != FAT_CACHE_VALID &&
	    new->id != MSDOS_I(inode)->cache_valid_id)
		goto out;	/* this cache was invalidated */

	cache = fat_cache_merge(inode, new);
	if (cache == NULL) {
		if (MSDOS_I(inode)->nr_caches < fat_max_cache(inode)) {
			MSDOS_I(inode)->nr_caches++;
			spin_unlock(&MSDOS_I(inode)->cache_lru_lock);

			tmp = fat_cache_alloc(inode);
			spin_lock(&MSDOS_I(inode)->cache_lru_lock);
			cache = fat_cache_merge(inode, new);
			if (cache != NULL) {
				MSDOS_I(inode)->nr_caches--;
				fat_cache_free(tmp);
				goto out_update_lru;
			}
			cache = tmp;
		} else {
			struct list_head *p = MSDOS_I(inode)->cache_lru.prev;
			cache = list_entry(p, struct fat_cache, cache_list);
		}
		cache->fcluster = new->fcluster;
		cache->dcluster = new->dcluster;
		cache->nr_contig = new->nr_contig;
	}
out_update_lru:
	fat_cache_update_lru(inode, cache);
out:
	spin_unlock(&MSDOS_I(inode)->cache_lru_lock);
}

/*
 * Cache invalidation occurs rarely, thus the LRU chain is not updated. It
 * fixes itself after a while.
 */
static void __fat_cache_inval_inode(struct inode *inode)
{
	struct msdos_inode_info *i = MSDOS_I(inode);
	struct fat_cache *cache;

	while (!list_empty(&i->cache_lru)) {
		cache = list_entry(i->cache_lru.next, struct fat_cache, cache_list);
		list_del_init(&cache->cache_list);
		i->nr_caches--;
		fat_cache_free(cache);
	}
	/* Update. The copy of caches before this id is discarded. */
	i->cache_valid_id++;
	if (i->cache_valid_id == FAT_CACHE_VALID)
		i->cache_valid_id++;
}

void fat_cache_inval_inode(struct inode *inode)
{
	spin_lock(&MSDOS_I(inode)->cache_lru_lock);
	__fat_cache_inval_inode(inode);
	spin_unlock(&MSDOS_I(inode)->cache_lru_lock);
}

static inline int cache_contiguous(struct fat_cache_id *cid, int dclus)
{
	cid->nr_contig++;
	return ((cid->dcluster + cid->nr_contig) == dclus);
}

static inline void cache_init(struct fat_cache_id *cid, int fclus, int dclus)
{
	cid->id = FAT_CACHE_VALID;
	cid->fcluster = fclus;
	cid->dcluster = dclus;
	cid->nr_contig = 0;
}

int fat_get_cluster(struct inode *inode, int cluster, int *fclus, int *dclus)
{
	struct super_block *sb = inode->i_sb;
	const int limit = sb->s_maxbytes >> MSDOS_SB(sb)->cluster_bits;
	struct fat_entry fatent;
	struct fat_cache_id cid;
	int nr;

	BUG_ON(MSDOS_I(inode)->i_start == 0);

	*fclus = 0;
	*dclus = MSDOS_I(inode)->i_start;
	if (cluster == 0)
		return 0;

	if (fat_cache_lookup(inode, cluster, &cid, fclus, dclus) < 0) {
		/*
		 * dummy, always not contiguous
		 * This is reinitialized by cache_init(), later.
		 */
		cache_init(&cid, -1, -1);
	}

	fatent_init(&fatent);
	while (*fclus < cluster) {
		/* prevent the infinite loop of cluster chain */
		if (*fclus > limit) {
			fat_fs_error(sb, "%s: detected the cluster chain loop"
				     " (i_pos %lld)", __func__,
				     MSDOS_I(inode)->i_pos);
			nr = -EIO;
			goto out;
		}

		nr = fat_ent_read(inode, &fatent, *dclus);
		if (nr < 0)
			goto out;
		else if (nr == FAT_ENT_FREE) {
			fat_fs_error(sb, "%s: invalid cluster chain"
				     " (i_pos %lld)", __func__,
				     MSDOS_I(inode)->i_pos);
			nr = -EIO;
			goto out;
		} else if (nr == FAT_ENT_EOF) {
			fat_cache_add(inode, &cid);
			goto out;
		}
		(*fclus)++;
		*dclus = nr;
		if (!cache_contiguous(&cid, *dclus))
			cache_init(&cid, *fclus, *dclus);
	}
	nr = 0;
	fat_cache_add(inode, &cid);
out:
	fatent_brelse(&fatent);
	return nr;
}

static int fat_bmap_cluster(struct inode *inode, int cluster)
{
	struct super_block *sb = inode->i_sb;
	int ret, fclus, dclus;

	if (MSDOS_I(inode)->i_start == 0)
		return 0;

	ret = fat_get_cluster(inode, cluster, &fclus, &dclus);
	if (ret < 0)
		return ret;
	else if (ret == FAT_ENT_EOF) {
		fat_fs_error(sb, "%s: request beyond EOF (i_pos %lld)",
			     __func__, MSDOS_I(inode)->i_pos);
		return -EIO;
	}
	return dclus;
}

int fat_bmap(struct inode *inode, sector_t sector, sector_t *phys,
	     unsigned long *mapped_blocks, int create)
{
	struct super_block *sb = inode->i_sb;
	struct msdos_sb_info *sbi = MSDOS_SB(sb);
	const unsigned long blocksize = sb->s_blocksize;
	const unsigned char blocksize_bits = sb->s_blocksize_bits;
	sector_t last_block;
	int cluster, offset;

	*phys = 0;
	*mapped_blocks = 0;
	if ((sbi->fat_bits != 32) && (inode->i_ino == MSDOS_ROOT_INO)) {
		if (sector < (sbi->dir_entries >> sbi->dir_per_block_bits)) {
			*phys = sector + sbi->dir_start;
			*mapped_blocks = 1;
		}
		return 0;
	}

	last_block = (i_size_read(inode) + (blocksize - 1)) >> blocksize_bits;
	if (sector >= last_block) {
		if (!create)
			return 0;

		/*
		 * ->mmu_private can access on only allocation path.
		 * (caller must hold ->i_mutex)
		 */
		last_block = (MSDOS_I(inode)->mmu_private + (blocksize - 1))
			>> blocksize_bits;
		if (sector >= last_block)
			return 0;
	}

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