[mirror_ubuntu-artful-kernel.git] / fs / mbcache.c

#include <linux/spinlock.h>
#include <linux/slab.h>
#include <linux/list.h>
#include <linux/list_bl.h>
#include <linux/module.h>
#include <linux/sched.h>
#include <linux/workqueue.h>
#include <linux/mbcache.h>

/*
 * Mbcache is a simple key-value store. Keys need not be unique, however
 * key-value pairs are expected to be unique (we use this fact in
 * mb_cache_entry_delete_block()).
 *
 * Ext2 and ext4 use this cache for deduplication of extended attribute blocks.
 * They use hash of a block contents as a key and block number as a value.
 * That's why keys need not be unique (different xattr blocks may end up having
 * the same hash). However block number always uniquely identifies a cache
 * entry.
 *
 * We provide functions for creation and removal of entries, search by key,
 * and a special "delete entry with given key-value pair" operation. Fixed
 * size hash table is used for fast key lookups.
 */

struct mb_cache {
	/* Hash table of entries */
	struct hlist_bl_head	*c_hash;
	/* log2 of hash table size */
	int			c_bucket_bits;
	/* Maximum entries in cache to avoid degrading hash too much */
	int			c_max_entries;
	/* Protects c_list, c_entry_count */
	spinlock_t		c_list_lock;
	struct list_head	c_list;
	/* Number of entries in cache */
	unsigned long		c_entry_count;
	struct shrinker		c_shrink;
	/* Work for shrinking when the cache has too many entries */
	struct work_struct	c_shrink_work;
};

static struct kmem_cache *mb_entry_cache;

static unsigned long mb_cache_shrink(struct mb_cache *cache,
				     unsigned int nr_to_scan);

static inline struct hlist_bl_head *mb_cache_entry_head(struct mb_cache *cache,
							u32 key)
{
	return &cache->c_hash[hash_32(key, cache->c_bucket_bits)];
}

/*
 * Number of entries to reclaim synchronously when there are too many entries
 * in cache
 */
#define SYNC_SHRINK_BATCH 64

/*
 * mb_cache_entry_create - create entry in cache
 * @cache - cache where the entry should be created
 * @mask - gfp mask with which the entry should be allocated
 * @key - key of the entry
 * @block - block that contains data
 *
 * Creates entry in @cache with key @key and records that data is stored in
 * block @block. The function returns -EBUSY if entry with the same key
 * and for the same block already exists in cache. Otherwise 0 is returned.
 */
int mb_cache_entry_create(struct mb_cache *cache, gfp_t mask, u32 key,
			  sector_t block)
{
	struct mb_cache_entry *entry, *dup;
	struct hlist_bl_node *dup_node;
	struct hlist_bl_head *head;

	/* Schedule background reclaim if there are too many entries */
	if (cache->c_entry_count >= cache->c_max_entries)
		schedule_work(&cache->c_shrink_work);
	/* Do some sync reclaim if background reclaim cannot keep up */
	if (cache->c_entry_count >= 2*cache->c_max_entries)
		mb_cache_shrink(cache, SYNC_SHRINK_BATCH);

	entry = kmem_cache_alloc(mb_entry_cache, mask);
	if (!entry)
		return -ENOMEM;

	INIT_LIST_HEAD(&entry->e_list);
	/* One ref for hash, one ref returned */
	atomic_set(&entry->e_refcnt, 1);
	entry->e_key = key;
	entry->e_block = block;
	head = mb_cache_entry_head(cache, key);
	hlist_bl_lock(head);
	hlist_bl_for_each_entry(dup, dup_node, head, e_hash_list) {
		if (dup->e_key == key && dup->e_block == block) {
			hlist_bl_unlock(head);
			kmem_cache_free(mb_entry_cache, entry);
			return -EBUSY;
		}
	}
	hlist_bl_add_head(&entry->e_hash_list, head);
	hlist_bl_unlock(head);

	spin_lock(&cache->c_list_lock);
	list_add_tail(&entry->e_list, &cache->c_list);
	/* Grab ref for LRU list */
	atomic_inc(&entry->e_refcnt);
	cache->c_entry_count++;
	spin_unlock(&cache->c_list_lock);

	return 0;
}
EXPORT_SYMBOL(mb_cache_entry_create);

void __mb_cache_entry_free(struct mb_cache_entry *entry)
{
	kmem_cache_free(mb_entry_cache, entry);
}
EXPORT_SYMBOL(__mb_cache_entry_free);

static struct mb_cache_entry *__entry_find(struct mb_cache *cache,
					   struct mb_cache_entry *entry,
					   u32 key)
{
	struct mb_cache_entry *old_entry = entry;
	struct hlist_bl_node *node;
	struct hlist_bl_head *head;

	head = mb_cache_entry_head(cache, key);
	hlist_bl_lock(head);
	if (entry && !hlist_bl_unhashed(&entry->e_hash_list))
		node = entry->e_hash_list.next;
	else
		node = hlist_bl_first(head);
	while (node) {
		entry = hlist_bl_entry(node, struct mb_cache_entry,
				       e_hash_list);
		if (entry->e_key == key) {
			atomic_inc(&entry->e_refcnt);
			goto out;
		}
		node = node->next;
	}
	entry = NULL;
out:
	hlist_bl_unlock(head);
	if (old_entry)
		mb_cache_entry_put(cache, old_entry);

	return entry;
}

/*
 * mb_cache_entry_find_first - find the first entry in cache with given key
 * @cache: cache where we should search
 * @key: key to look for
 *
 * Search in @cache for entry with key @key. Grabs reference to the first
 * entry found and returns the entry.
 */
struct mb_cache_entry *mb_cache_entry_find_first(struct mb_cache *cache,
						 u32 key)
{
	return __entry_find(cache, NULL, key);
}
EXPORT_SYMBOL(mb_cache_entry_find_first);

/*
 * mb_cache_entry_find_next - find next entry in cache with the same
 * @cache: cache where we should search
 * @entry: entry to start search from
 *
 * Finds next entry in the hash chain which has the same key as @entry.
 * If @entry is unhashed (which can happen when deletion of entry races
 * with the search), finds the first entry in the hash chain. The function
 * drops reference to @entry and returns with a reference to the found entry.
 */
struct mb_cache_entry *mb_cache_entry_find_next(struct mb_cache *cache,
						struct mb_cache_entry *entry)
{
	return __entry_find(cache, entry, entry->e_key);
}
EXPORT_SYMBOL(mb_cache_entry_find_next);

/* mb_cache_entry_delete_block - remove information about block from cache
 * @cache - cache we work with
 * @key - key of the entry to remove
 * @block - block containing data for @key
 *
 * Remove entry from cache @cache with key @key with data stored in @block.
 */
void mb_cache_entry_delete_block(struct mb_cache *cache, u32 key,
				 sector_t block)
{
	struct hlist_bl_node *node;
	struct hlist_bl_head *head;
	struct mb_cache_entry *entry;

	head = mb_cache_entry_head(cache, key);
	hlist_bl_lock(head);
	hlist_bl_for_each_entry(entry, node, head, e_hash_list) {
		if (entry->e_key == key && entry->e_block == block) {
			/* We keep hash list reference to keep entry alive */
			hlist_bl_del_init(&entry->e_hash_list);
			hlist_bl_unlock(head);
			spin_lock(&cache->c_list_lock);
			if (!list_empty(&entry->e_list)) {
				list_del_init(&entry->e_list);
				cache->c_entry_count--;
				atomic_dec(&entry->e_refcnt);
			}
			spin_unlock(&cache->c_list_lock);
			mb_cache_entry_put(cache, entry);
			return;
		}
	}
	hlist_bl_unlock(head);
}
EXPORT_SYMBOL(mb_cache_entry_delete_block);

/* mb_cache_entry_touch - cache entry got used
 * @cache - cache the entry belongs to
 * @entry - entry that got used
 *
 * Marks entry as used to give hit higher chances of surviving in cache.
 */
void mb_cache_entry_touch(struct mb_cache *cache,
			  struct mb_cache_entry *entry)
{
	entry->e_referenced = 1;
}
EXPORT_SYMBOL(mb_cache_entry_touch);

static unsigned long mb_cache_count(struct shrinker *shrink,
				    struct shrink_control *sc)
{
	struct mb_cache *cache = container_of(shrink, struct mb_cache,
					      c_shrink);

	return cache->c_entry_count;
}

/* Shrink number of entries in cache */
static unsigned long mb_cache_shrink(struct mb_cache *cache,
				     unsigned int nr_to_scan)
{
	struct mb_cache_entry *entry;
	struct hlist_bl_head *head;
	unsigned int shrunk = 0;

	spin_lock(&cache->c_list_lock);
	while (nr_to_scan-- && !list_empty(&cache->c_list)) {
		entry = list_first_entry(&cache->c_list,
					 struct mb_cache_entry, e_list);
		if (entry->e_referenced) {
			entry->e_referenced = 0;
			list_move_tail(&cache->c_list, &entry->e_list);
			continue;
		}
		list_del_init(&entry->e_list);
		cache->c_entry_count--;
		/*
		 * We keep LRU list reference so that entry doesn't go away
		 * from under us.
		 */
		spin_unlock(&cache->c_list_lock);
		head = mb_cache_entry_head(cache, entry->e_key);
		hlist_bl_lock(head);
		if (!hlist_bl_unhashed(&entry->e_hash_list)) {
			hlist_bl_del_init(&entry->e_hash_list);
			atomic_dec(&entry->e_refcnt);
		}
		hlist_bl_unlock(head);
		if (mb_cache_entry_put(cache, entry))
			shrunk++;
		cond_resched();
		spin_lock(&cache->c_list_lock);
	}
	spin_unlock(&cache->c_list_lock);

	return shrunk;
}

static unsigned long mb_cache_scan(struct shrinker *shrink,
				   struct shrink_control *sc)
{
	int nr_to_scan = sc->nr_to_scan;
	struct mb_cache *cache = container_of(shrink, struct mb_cache,
					      c_shrink);
	return mb_cache_shrink(cache, nr_to_scan);
}

/* We shrink 1/X of the cache when we have too many entries in it */
#define SHRINK_DIVISOR 16

static void mb_cache_shrink_worker(struct work_struct *work)
{
	struct mb_cache *cache = container_of(work, struct mb_cache,
					      c_shrink_work);
	mb_cache_shrink(cache, cache->c_max_entries / SHRINK_DIVISOR);
}

/*
 * mb_cache_create - create cache
 * @bucket_bits: log2 of the hash table size
 *
 * Create cache for keys with 2^bucket_bits hash entries.
 */
struct mb_cache *mb_cache_create(int bucket_bits)
{
	struct mb_cache *cache;
	int bucket_count = 1 << bucket_bits;
	int i;

	if (!try_module_get(THIS_MODULE))
		return NULL;

	cache = kzalloc(sizeof(struct mb_cache), GFP_KERNEL);
	if (!cache)
		goto err_out;
	cache->c_bucket_bits = bucket_bits;
	cache->c_max_entries = bucket_count << 4;
	INIT_LIST_HEAD(&cache->c_list);
	spin_lock_init(&cache->c_list_lock);
	cache->c_hash = kmalloc(bucket_count * sizeof(struct hlist_bl_head),
				GFP_KERNEL);
	if (!cache->c_hash) {
		kfree(cache);
		goto err_out;
	}
	for (i = 0; i < bucket_count; i++)
		INIT_HLIST_BL_HEAD(&cache->c_hash[i]);

	cache->c_shrink.count_objects = mb_cache_count;
	cache->c_shrink.scan_objects = mb_cache_scan;
	cache->c_shrink.seeks = DEFAULT_SEEKS;
	register_shrinker(&cache->c_shrink);

	INIT_WORK(&cache->c_shrink_work, mb_cache_shrink_worker);

	return cache;

err_out:
	module_put(THIS_MODULE);
	return NULL;
}
EXPORT_SYMBOL(mb_cache_create);

/*
 * mb_cache_destroy - destroy cache
 * @cache: the cache to destroy
 *
 * Free all entries in cache and cache itself. Caller must make sure nobody
 * (except shrinker) can reach @cache when calling this.
 */
void mb_cache_destroy(struct mb_cache *cache)
{
	struct mb_cache_entry *entry, *next;

	unregister_shrinker(&cache->c_shrink);

	/*
	 * We don't bother with any locking. Cache must not be used at this
	 * point.
	 */
	list_for_each_entry_safe(entry, next, &cache->c_list, e_list) {
		if (!hlist_bl_unhashed(&entry->e_hash_list)) {
			hlist_bl_del_init(&entry->e_hash_list);
			atomic_dec(&entry->e_refcnt);
		} else
			WARN_ON(1);
		list_del(&entry->e_list);
		WARN_ON(atomic_read(&entry->e_refcnt) != 1);
		mb_cache_entry_put(cache, entry);
	}
	kfree(cache->c_hash);
	kfree(cache);
	module_put(THIS_MODULE);
}
EXPORT_SYMBOL(mb_cache_destroy);

static int __init mbcache_init(void)
{
	mb_entry_cache = kmem_cache_create("mbcache",
				sizeof(struct mb_cache_entry), 0,
				SLAB_RECLAIM_ACCOUNT|SLAB_MEM_SPREAD, NULL);
	BUG_ON(!mb_entry_cache);
	return 0;
}

static void __exit mbcache_exit(void)
{
	kmem_cache_destroy(mb_entry_cache);
}

module_init(mbcache_init)
module_exit(mbcache_exit)

MODULE_AUTHOR("Jan Kara <jack@suse.cz>");
MODULE_DESCRIPTION("Meta block cache (for extended attributes)");
MODULE_LICENSE("GPL");
Commit	Line	Data
f9a61eb4 JK	1	#include <linux/spinlock.h>
	2	#include <linux/slab.h>
	3	#include <linux/list.h>
	4	#include <linux/list_bl.h>
	5	#include <linux/module.h>
	6	#include <linux/sched.h>
c2f3140f	7	#include <linux/workqueue.h>
7a2508e1	8	#include <linux/mbcache.h>
f9a61eb4 JK	9
	10	/*
	11	* Mbcache is a simple key-value store. Keys need not be unique, however
	12	* key-value pairs are expected to be unique (we use this fact in
7a2508e1	13	* mb_cache_entry_delete_block()).
f9a61eb4 JK	14	*
	15	* Ext2 and ext4 use this cache for deduplication of extended attribute blocks.
	16	* They use hash of a block contents as a key and block number as a value.
	17	* That's why keys need not be unique (different xattr blocks may end up having
	18	* the same hash). However block number always uniquely identifies a cache
	19	* entry.
	20	*
	21	* We provide functions for creation and removal of entries, search by key,
	22	* and a special "delete entry with given key-value pair" operation. Fixed
	23	* size hash table is used for fast key lookups.
	24	*/
	25
7a2508e1	26	struct mb_cache {
f9a61eb4 JK	27	/* Hash table of entries */
	28	struct hlist_bl_head *c_hash;
	29	/* log2 of hash table size */
	30	int c_bucket_bits;
c2f3140f JK	31	/* Maximum entries in cache to avoid degrading hash too much */
c2f3140f JK	32	int c_max_entries;
f0c8b462 JK	33	/* Protects c_list, c_entry_count */
	34	spinlock_t c_list_lock;
	35	struct list_head c_list;
f9a61eb4 JK	36	/* Number of entries in cache */
	37	unsigned long c_entry_count;
	38	struct shrinker c_shrink;
c2f3140f JK	39	/* Work for shrinking when the cache has too many entries */
c2f3140f JK	40	struct work_struct c_shrink_work;
f9a61eb4 JK	41	};
f9a61eb4 JK	42
7a2508e1	43	static struct kmem_cache *mb_entry_cache;
f9a61eb4	44
7a2508e1 JK	45	static unsigned long mb_cache_shrink(struct mb_cache *cache,
7a2508e1 JK	46	unsigned int nr_to_scan);
c2f3140f	47
dc8d5e56 AG	48	static inline struct hlist_bl_head mb_cache_entry_head(struct mb_cache cache,
dc8d5e56 AG	49	u32 key)
f0c8b462	50	{
dc8d5e56	51	return &cache->c_hash[hash_32(key, cache->c_bucket_bits)];
f0c8b462 JK	52	}
f0c8b462 JK	53
c2f3140f JK	54	/*
	55	* Number of entries to reclaim synchronously when there are too many entries
	56	* in cache
	57	*/
	58	#define SYNC_SHRINK_BATCH 64
	59
f9a61eb4	60	/*
7a2508e1	61	* mb_cache_entry_create - create entry in cache
f9a61eb4 JK	62	* @cache - cache where the entry should be created
	63	* @mask - gfp mask with which the entry should be allocated
	64	* @key - key of the entry
	65	* @block - block that contains data
	66	*
	67	* Creates entry in @cache with key @key and records that data is stored in
	68	* block @block. The function returns -EBUSY if entry with the same key
	69	* and for the same block already exists in cache. Otherwise 0 is returned.
	70	*/
7a2508e1 JK	71	int mb_cache_entry_create(struct mb_cache *cache, gfp_t mask, u32 key,
7a2508e1 JK	72	sector_t block)
f9a61eb4	73	{
7a2508e1	74	struct mb_cache_entry entry, dup;
f9a61eb4 JK	75	struct hlist_bl_node *dup_node;
	76	struct hlist_bl_head *head;
	77
c2f3140f JK	78	/* Schedule background reclaim if there are too many entries */
	79	if (cache->c_entry_count >= cache->c_max_entries)
	80	schedule_work(&cache->c_shrink_work);
	81	/* Do some sync reclaim if background reclaim cannot keep up */
	82	if (cache->c_entry_count >= 2*cache->c_max_entries)
7a2508e1	83	mb_cache_shrink(cache, SYNC_SHRINK_BATCH);
c2f3140f	84
7a2508e1	85	entry = kmem_cache_alloc(mb_entry_cache, mask);
f9a61eb4 JK	86	if (!entry)
	87	return -ENOMEM;
	88
f0c8b462	89	INIT_LIST_HEAD(&entry->e_list);
f9a61eb4 JK	90	/* One ref for hash, one ref returned */
	91	atomic_set(&entry->e_refcnt, 1);
	92	entry->e_key = key;
	93	entry->e_block = block;
dc8d5e56	94	head = mb_cache_entry_head(cache, key);
f9a61eb4 JK	95	hlist_bl_lock(head);
	96	hlist_bl_for_each_entry(dup, dup_node, head, e_hash_list) {
	97	if (dup->e_key == key && dup->e_block == block) {
	98	hlist_bl_unlock(head);
7a2508e1	99	kmem_cache_free(mb_entry_cache, entry);
f9a61eb4 JK	100	return -EBUSY;
	101	}
	102	}
	103	hlist_bl_add_head(&entry->e_hash_list, head);
	104	hlist_bl_unlock(head);
	105
f0c8b462 JK	106	spin_lock(&cache->c_list_lock);
f0c8b462 JK	107	list_add_tail(&entry->e_list, &cache->c_list);
f9a61eb4 JK	108	/* Grab ref for LRU list */
	109	atomic_inc(&entry->e_refcnt);
	110	cache->c_entry_count++;
f0c8b462	111	spin_unlock(&cache->c_list_lock);
f9a61eb4 JK	112
	113	return 0;
	114	}
7a2508e1	115	EXPORT_SYMBOL(mb_cache_entry_create);
f9a61eb4	116
7a2508e1	117	void __mb_cache_entry_free(struct mb_cache_entry *entry)
f9a61eb4	118	{
7a2508e1	119	kmem_cache_free(mb_entry_cache, entry);
f9a61eb4	120	}
7a2508e1	121	EXPORT_SYMBOL(__mb_cache_entry_free);
f9a61eb4	122
7a2508e1 JK	123	static struct mb_cache_entry __entry_find(struct mb_cache cache,
	124	struct mb_cache_entry *entry,
	125	u32 key)
f9a61eb4	126	{
7a2508e1	127	struct mb_cache_entry *old_entry = entry;
f9a61eb4 JK	128	struct hlist_bl_node *node;
	129	struct hlist_bl_head *head;
	130
dc8d5e56	131	head = mb_cache_entry_head(cache, key);
f9a61eb4 JK	132	hlist_bl_lock(head);
	133	if (entry && !hlist_bl_unhashed(&entry->e_hash_list))
	134	node = entry->e_hash_list.next;
	135	else
	136	node = hlist_bl_first(head);
	137	while (node) {
7a2508e1	138	entry = hlist_bl_entry(node, struct mb_cache_entry,
f9a61eb4 JK	139	e_hash_list);
	140	if (entry->e_key == key) {
	141	atomic_inc(&entry->e_refcnt);
	142	goto out;
	143	}
	144	node = node->next;
	145	}
	146	entry = NULL;
	147	out:
	148	hlist_bl_unlock(head);
	149	if (old_entry)
7a2508e1	150	mb_cache_entry_put(cache, old_entry);
f9a61eb4 JK	151
	152	return entry;
	153	}
	154
	155	/*
7a2508e1	156	* mb_cache_entry_find_first - find the first entry in cache with given key
f9a61eb4 JK	157	* @cache: cache where we should search
	158	* @key: key to look for
	159	*
	160	* Search in @cache for entry with key @key. Grabs reference to the first
	161	* entry found and returns the entry.
	162	*/
7a2508e1 JK	163	struct mb_cache_entry mb_cache_entry_find_first(struct mb_cache cache,
7a2508e1 JK	164	u32 key)
f9a61eb4 JK	165	{
	166	return __entry_find(cache, NULL, key);
	167	}
7a2508e1	168	EXPORT_SYMBOL(mb_cache_entry_find_first);
f9a61eb4 JK	169
f9a61eb4 JK	170	/*
7a2508e1	171	* mb_cache_entry_find_next - find next entry in cache with the same
f9a61eb4 JK	172	* @cache: cache where we should search
	173	* @entry: entry to start search from
	174	*
	175	* Finds next entry in the hash chain which has the same key as @entry.
	176	* If @entry is unhashed (which can happen when deletion of entry races
	177	* with the search), finds the first entry in the hash chain. The function
	178	* drops reference to @entry and returns with a reference to the found entry.
	179	*/
7a2508e1 JK	180	struct mb_cache_entry mb_cache_entry_find_next(struct mb_cache cache,
7a2508e1 JK	181	struct mb_cache_entry *entry)
f9a61eb4 JK	182	{
	183	return __entry_find(cache, entry, entry->e_key);
	184	}
7a2508e1	185	EXPORT_SYMBOL(mb_cache_entry_find_next);
f9a61eb4	186
7a2508e1	187	/* mb_cache_entry_delete_block - remove information about block from cache
f9a61eb4 JK	188	* @cache - cache we work with
	189	* @key - key of the entry to remove
	190	* @block - block containing data for @key
	191	*
	192	* Remove entry from cache @cache with key @key with data stored in @block.
	193	*/
7a2508e1 JK	194	void mb_cache_entry_delete_block(struct mb_cache *cache, u32 key,
7a2508e1 JK	195	sector_t block)
f9a61eb4 JK	196	{
	197	struct hlist_bl_node *node;
	198	struct hlist_bl_head *head;
7a2508e1	199	struct mb_cache_entry *entry;
f9a61eb4	200
dc8d5e56	201	head = mb_cache_entry_head(cache, key);
f9a61eb4 JK	202	hlist_bl_lock(head);
	203	hlist_bl_for_each_entry(entry, node, head, e_hash_list) {
	204	if (entry->e_key == key && entry->e_block == block) {
	205	/* We keep hash list reference to keep entry alive */
	206	hlist_bl_del_init(&entry->e_hash_list);
	207	hlist_bl_unlock(head);
f0c8b462 JK	208	spin_lock(&cache->c_list_lock);
	209	if (!list_empty(&entry->e_list)) {
	210	list_del_init(&entry->e_list);
f9a61eb4 JK	211	cache->c_entry_count--;
	212	atomic_dec(&entry->e_refcnt);
	213	}
f0c8b462	214	spin_unlock(&cache->c_list_lock);
7a2508e1	215	mb_cache_entry_put(cache, entry);
f9a61eb4 JK	216	return;
	217	}
	218	}
	219	hlist_bl_unlock(head);
	220	}
7a2508e1	221	EXPORT_SYMBOL(mb_cache_entry_delete_block);
f9a61eb4	222
7a2508e1	223	/* mb_cache_entry_touch - cache entry got used
f9a61eb4 JK	224	* @cache - cache the entry belongs to
	225	* @entry - entry that got used
	226	*
f0c8b462	227	* Marks entry as used to give hit higher chances of surviving in cache.
f9a61eb4	228	*/
7a2508e1 JK	229	void mb_cache_entry_touch(struct mb_cache *cache,
7a2508e1 JK	230	struct mb_cache_entry *entry)
f9a61eb4	231	{
dc8d5e56	232	entry->e_referenced = 1;
f9a61eb4	233	}
7a2508e1	234	EXPORT_SYMBOL(mb_cache_entry_touch);
f9a61eb4	235
7a2508e1 JK	236	static unsigned long mb_cache_count(struct shrinker *shrink,
7a2508e1 JK	237	struct shrink_control *sc)
f9a61eb4	238	{
7a2508e1 JK	239	struct mb_cache *cache = container_of(shrink, struct mb_cache,
7a2508e1 JK	240	c_shrink);
f9a61eb4 JK	241
	242	return cache->c_entry_count;
	243	}
	244
	245	/* Shrink number of entries in cache */
7a2508e1 JK	246	static unsigned long mb_cache_shrink(struct mb_cache *cache,
7a2508e1 JK	247	unsigned int nr_to_scan)
f9a61eb4	248	{
7a2508e1	249	struct mb_cache_entry *entry;
f9a61eb4 JK	250	struct hlist_bl_head *head;
	251	unsigned int shrunk = 0;
	252
f0c8b462 JK	253	spin_lock(&cache->c_list_lock);
	254	while (nr_to_scan-- && !list_empty(&cache->c_list)) {
	255	entry = list_first_entry(&cache->c_list,
7a2508e1	256	struct mb_cache_entry, e_list);
dc8d5e56 AG	257	if (entry->e_referenced) {
dc8d5e56 AG	258	entry->e_referenced = 0;
f0c8b462 JK	259	list_move_tail(&cache->c_list, &entry->e_list);
	260	continue;
	261	}
	262	list_del_init(&entry->e_list);
f9a61eb4 JK	263	cache->c_entry_count--;
	264	/*
	265	* We keep LRU list reference so that entry doesn't go away
	266	* from under us.
	267	*/
f0c8b462	268	spin_unlock(&cache->c_list_lock);
dc8d5e56	269	head = mb_cache_entry_head(cache, entry->e_key);
f9a61eb4 JK	270	hlist_bl_lock(head);
	271	if (!hlist_bl_unhashed(&entry->e_hash_list)) {
	272	hlist_bl_del_init(&entry->e_hash_list);
	273	atomic_dec(&entry->e_refcnt);
	274	}
	275	hlist_bl_unlock(head);
7a2508e1	276	if (mb_cache_entry_put(cache, entry))
f9a61eb4 JK	277	shrunk++;
f9a61eb4 JK	278	cond_resched();
f0c8b462	279	spin_lock(&cache->c_list_lock);
f9a61eb4	280	}
f0c8b462	281	spin_unlock(&cache->c_list_lock);
f9a61eb4 JK	282
	283	return shrunk;
	284	}
	285
7a2508e1 JK	286	static unsigned long mb_cache_scan(struct shrinker *shrink,
7a2508e1 JK	287	struct shrink_control *sc)
c2f3140f JK	288	{
c2f3140f JK	289	int nr_to_scan = sc->nr_to_scan;
7a2508e1	290	struct mb_cache *cache = container_of(shrink, struct mb_cache,
c2f3140f	291	c_shrink);
7a2508e1	292	return mb_cache_shrink(cache, nr_to_scan);
c2f3140f JK	293	}
	294
	295	/* We shrink 1/X of the cache when we have too many entries in it */
	296	#define SHRINK_DIVISOR 16
	297
7a2508e1	298	static void mb_cache_shrink_worker(struct work_struct *work)
c2f3140f	299	{
7a2508e1 JK	300	struct mb_cache *cache = container_of(work, struct mb_cache,
	301	c_shrink_work);
	302	mb_cache_shrink(cache, cache->c_max_entries / SHRINK_DIVISOR);
c2f3140f JK	303	}
c2f3140f JK	304
f9a61eb4	305	/*
7a2508e1	306	* mb_cache_create - create cache
f9a61eb4 JK	307	* @bucket_bits: log2 of the hash table size
	308	*
	309	* Create cache for keys with 2^bucket_bits hash entries.
	310	*/
7a2508e1	311	struct mb_cache *mb_cache_create(int bucket_bits)
f9a61eb4	312	{
7a2508e1	313	struct mb_cache *cache;
f9a61eb4 JK	314	int bucket_count = 1 << bucket_bits;
	315	int i;
	316
	317	if (!try_module_get(THIS_MODULE))
	318	return NULL;
	319
7a2508e1	320	cache = kzalloc(sizeof(struct mb_cache), GFP_KERNEL);
f9a61eb4 JK	321	if (!cache)
	322	goto err_out;
	323	cache->c_bucket_bits = bucket_bits;
c2f3140f	324	cache->c_max_entries = bucket_count << 4;
f0c8b462 JK	325	INIT_LIST_HEAD(&cache->c_list);
f0c8b462 JK	326	spin_lock_init(&cache->c_list_lock);
f9a61eb4 JK	327	cache->c_hash = kmalloc(bucket_count * sizeof(struct hlist_bl_head),
	328	GFP_KERNEL);
	329	if (!cache->c_hash) {
	330	kfree(cache);
	331	goto err_out;
	332	}
	333	for (i = 0; i < bucket_count; i++)
	334	INIT_HLIST_BL_HEAD(&cache->c_hash[i]);
	335
7a2508e1 JK	336	cache->c_shrink.count_objects = mb_cache_count;
7a2508e1 JK	337	cache->c_shrink.scan_objects = mb_cache_scan;
f9a61eb4 JK	338	cache->c_shrink.seeks = DEFAULT_SEEKS;
	339	register_shrinker(&cache->c_shrink);
	340
7a2508e1	341	INIT_WORK(&cache->c_shrink_work, mb_cache_shrink_worker);
c2f3140f	342
f9a61eb4 JK	343	return cache;
	344
	345	err_out:
	346	module_put(THIS_MODULE);
	347	return NULL;
	348	}
7a2508e1	349	EXPORT_SYMBOL(mb_cache_create);
f9a61eb4 JK	350
f9a61eb4 JK	351	/*
7a2508e1	352	* mb_cache_destroy - destroy cache
f9a61eb4 JK	353	* @cache: the cache to destroy
	354	*
	355	* Free all entries in cache and cache itself. Caller must make sure nobody
	356	* (except shrinker) can reach @cache when calling this.
	357	*/
7a2508e1	358	void mb_cache_destroy(struct mb_cache *cache)
f9a61eb4	359	{
7a2508e1	360	struct mb_cache_entry entry, next;
f9a61eb4 JK	361
	362	unregister_shrinker(&cache->c_shrink);
	363
	364	/*
	365	* We don't bother with any locking. Cache must not be used at this
	366	* point.
	367	*/
f0c8b462	368	list_for_each_entry_safe(entry, next, &cache->c_list, e_list) {
f9a61eb4 JK	369	if (!hlist_bl_unhashed(&entry->e_hash_list)) {
	370	hlist_bl_del_init(&entry->e_hash_list);
	371	atomic_dec(&entry->e_refcnt);
	372	} else
	373	WARN_ON(1);
f0c8b462	374	list_del(&entry->e_list);
f9a61eb4	375	WARN_ON(atomic_read(&entry->e_refcnt) != 1);
7a2508e1	376	mb_cache_entry_put(cache, entry);
f9a61eb4 JK	377	}
	378	kfree(cache->c_hash);
	379	kfree(cache);
	380	module_put(THIS_MODULE);
	381	}
7a2508e1	382	EXPORT_SYMBOL(mb_cache_destroy);
f9a61eb4	383
7a2508e1	384	static int __init mbcache_init(void)
f9a61eb4	385	{
7a2508e1 JK	386	mb_entry_cache = kmem_cache_create("mbcache",
7a2508e1 JK	387	sizeof(struct mb_cache_entry), 0,
f9a61eb4	388	SLAB_RECLAIM_ACCOUNT\|SLAB_MEM_SPREAD, NULL);
7a2508e1	389	BUG_ON(!mb_entry_cache);
f9a61eb4 JK	390	return 0;
	391	}
	392
7a2508e1	393	static void __exit mbcache_exit(void)
f9a61eb4	394	{
7a2508e1	395	kmem_cache_destroy(mb_entry_cache);
f9a61eb4 JK	396	}
f9a61eb4 JK	397
7a2508e1 JK	398	module_init(mbcache_init)
7a2508e1 JK	399	module_exit(mbcache_exit)
f9a61eb4 JK	400
	401	MODULE_AUTHOR("Jan Kara <jack@suse.cz>");
	402	MODULE_DESCRIPTION("Meta block cache (for extended attributes)");
	403	MODULE_LICENSE("GPL");