[deliverable/linux.git] / mm / list_lru.c

/*
 * Copyright (c) 2013 Red Hat, Inc. and Parallels Inc. All rights reserved.
 * Authors: David Chinner and Glauber Costa
 *
 * Generic LRU infrastructure
 */
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/mm.h>
#include <linux/list_lru.h>
#include <linux/slab.h>

bool list_lru_add(struct list_lru *lru, struct list_head *item)
{
	int nid = page_to_nid(virt_to_page(item));
	struct list_lru_node *nlru = &lru->node[nid];

	spin_lock(&nlru->lock);
	WARN_ON_ONCE(nlru->nr_items < 0);
	if (list_empty(item)) {
		list_add_tail(item, &nlru->list);
		if (nlru->nr_items++ == 0)
			node_set(nid, lru->active_nodes);
		spin_unlock(&nlru->lock);
		return true;
	}
	spin_unlock(&nlru->lock);
	return false;
}
EXPORT_SYMBOL_GPL(list_lru_add);

bool list_lru_del(struct list_lru *lru, struct list_head *item)
{
	int nid = page_to_nid(virt_to_page(item));
	struct list_lru_node *nlru = &lru->node[nid];

	spin_lock(&nlru->lock);
	if (!list_empty(item)) {
		list_del_init(item);
		if (--nlru->nr_items == 0)
			node_clear(nid, lru->active_nodes);
		WARN_ON_ONCE(nlru->nr_items < 0);
		spin_unlock(&nlru->lock);
		return true;
	}
	spin_unlock(&nlru->lock);
	return false;
}
EXPORT_SYMBOL_GPL(list_lru_del);

unsigned long
list_lru_count_node(struct list_lru *lru, int nid)
{
	unsigned long count = 0;
	struct list_lru_node *nlru = &lru->node[nid];

	spin_lock(&nlru->lock);
	WARN_ON_ONCE(nlru->nr_items < 0);
	count += nlru->nr_items;
	spin_unlock(&nlru->lock);

	return count;
}
EXPORT_SYMBOL_GPL(list_lru_count_node);

unsigned long
list_lru_walk_node(struct list_lru *lru, int nid, list_lru_walk_cb isolate,
		   void *cb_arg, unsigned long *nr_to_walk)
{

	struct list_lru_node	*nlru = &lru->node[nid];
	struct list_head *item, *n;
	unsigned long isolated = 0;

	spin_lock(&nlru->lock);
restart:
	list_for_each_safe(item, n, &nlru->list) {
		enum lru_status ret;

		/*
		 * decrement nr_to_walk first so that we don't livelock if we
		 * get stuck on large numbesr of LRU_RETRY items
		 */
		if (!*nr_to_walk)
			break;
		--*nr_to_walk;

		ret = isolate(item, &nlru->lock, cb_arg);
		switch (ret) {
		case LRU_REMOVED_RETRY:
			assert_spin_locked(&nlru->lock);
		case LRU_REMOVED:
			if (--nlru->nr_items == 0)
				node_clear(nid, lru->active_nodes);
			WARN_ON_ONCE(nlru->nr_items < 0);
			isolated++;
			/*
			 * If the lru lock has been dropped, our list
			 * traversal is now invalid and so we have to
			 * restart from scratch.
			 */
			if (ret == LRU_REMOVED_RETRY)
				goto restart;
			break;
		case LRU_ROTATE:
			list_move_tail(item, &nlru->list);
			break;
		case LRU_SKIP:
			break;
		case LRU_RETRY:
			/*
			 * The lru lock has been dropped, our list traversal is
			 * now invalid and so we have to restart from scratch.
			 */
			assert_spin_locked(&nlru->lock);
			goto restart;
		default:
			BUG();
		}
	}

	spin_unlock(&nlru->lock);
	return isolated;
}
EXPORT_SYMBOL_GPL(list_lru_walk_node);

int list_lru_init_key(struct list_lru *lru, struct lock_class_key *key)
{
	int i;
	size_t size = sizeof(*lru->node) * nr_node_ids;

	lru->node = kzalloc(size, GFP_KERNEL);
	if (!lru->node)
		return -ENOMEM;

	nodes_clear(lru->active_nodes);
	for (i = 0; i < nr_node_ids; i++) {
		spin_lock_init(&lru->node[i].lock);
		if (key)
			lockdep_set_class(&lru->node[i].lock, key);
		INIT_LIST_HEAD(&lru->node[i].list);
		lru->node[i].nr_items = 0;
	}
	return 0;
}
EXPORT_SYMBOL_GPL(list_lru_init_key);

void list_lru_destroy(struct list_lru *lru)
{
	kfree(lru->node);
}
EXPORT_SYMBOL_GPL(list_lru_destroy);
Commit	Line	Data
a38e4082 DC	1	/*
	2	* Copyright (c) 2013 Red Hat, Inc. and Parallels Inc. All rights reserved.
	3	* Authors: David Chinner and Glauber Costa
	4	*
	5	* Generic LRU infrastructure
	6	*/
	7	#include <linux/kernel.h>
	8	#include <linux/module.h>
3b1d58a4	9	#include <linux/mm.h>
a38e4082	10	#include <linux/list_lru.h>
5ca302c8	11	#include <linux/slab.h>
a38e4082 DC	12
	13	bool list_lru_add(struct list_lru lru, struct list_head item)
	14	{
3b1d58a4 DC	15	int nid = page_to_nid(virt_to_page(item));
	16	struct list_lru_node *nlru = &lru->node[nid];
	17
	18	spin_lock(&nlru->lock);
	19	WARN_ON_ONCE(nlru->nr_items < 0);
a38e4082	20	if (list_empty(item)) {
3b1d58a4 DC	21	list_add_tail(item, &nlru->list);
	22	if (nlru->nr_items++ == 0)
	23	node_set(nid, lru->active_nodes);
	24	spin_unlock(&nlru->lock);
a38e4082 DC	25	return true;
a38e4082 DC	26	}
3b1d58a4	27	spin_unlock(&nlru->lock);
a38e4082 DC	28	return false;
	29	}
	30	EXPORT_SYMBOL_GPL(list_lru_add);
	31
	32	bool list_lru_del(struct list_lru lru, struct list_head item)
	33	{
3b1d58a4 DC	34	int nid = page_to_nid(virt_to_page(item));
	35	struct list_lru_node *nlru = &lru->node[nid];
	36
	37	spin_lock(&nlru->lock);
a38e4082 DC	38	if (!list_empty(item)) {
a38e4082 DC	39	list_del_init(item);
3b1d58a4 DC	40	if (--nlru->nr_items == 0)
	41	node_clear(nid, lru->active_nodes);
	42	WARN_ON_ONCE(nlru->nr_items < 0);
	43	spin_unlock(&nlru->lock);
a38e4082 DC	44	return true;
a38e4082 DC	45	}
3b1d58a4	46	spin_unlock(&nlru->lock);
a38e4082 DC	47	return false;
	48	}
	49	EXPORT_SYMBOL_GPL(list_lru_del);
	50
6a4f496f GC	51	unsigned long
6a4f496f GC	52	list_lru_count_node(struct list_lru *lru, int nid)
a38e4082	53	{
3b1d58a4	54	unsigned long count = 0;
6a4f496f	55	struct list_lru_node *nlru = &lru->node[nid];
3b1d58a4	56
6a4f496f GC	57	spin_lock(&nlru->lock);
	58	WARN_ON_ONCE(nlru->nr_items < 0);
	59	count += nlru->nr_items;
	60	spin_unlock(&nlru->lock);
3b1d58a4 DC	61
	62	return count;
	63	}
6a4f496f	64	EXPORT_SYMBOL_GPL(list_lru_count_node);
3b1d58a4	65
6a4f496f	66	unsigned long
3b1d58a4 DC	67	list_lru_walk_node(struct list_lru *lru, int nid, list_lru_walk_cb isolate,
	68	void cb_arg, unsigned long nr_to_walk)
	69	{
	70
	71	struct list_lru_node *nlru = &lru->node[nid];
a38e4082	72	struct list_head item, n;
3b1d58a4	73	unsigned long isolated = 0;
a38e4082	74
3b1d58a4	75	spin_lock(&nlru->lock);
a38e4082	76	restart:
3b1d58a4	77	list_for_each_safe(item, n, &nlru->list) {
a38e4082	78	enum lru_status ret;
5cedf721 DC	79
	80	/*
	81	* decrement nr_to_walk first so that we don't livelock if we
	82	* get stuck on large numbesr of LRU_RETRY items
	83	*/
c56b097a	84	if (!*nr_to_walk)
5cedf721	85	break;
c56b097a	86	--*nr_to_walk;
5cedf721	87
3b1d58a4	88	ret = isolate(item, &nlru->lock, cb_arg);
a38e4082	89	switch (ret) {
449dd698 JW	90	case LRU_REMOVED_RETRY:
449dd698 JW	91	assert_spin_locked(&nlru->lock);
a38e4082	92	case LRU_REMOVED:
3b1d58a4 DC	93	if (--nlru->nr_items == 0)
	94	node_clear(nid, lru->active_nodes);
	95	WARN_ON_ONCE(nlru->nr_items < 0);
	96	isolated++;
449dd698 JW	97	/*
	98	* If the lru lock has been dropped, our list
	99	* traversal is now invalid and so we have to
	100	* restart from scratch.
	101	*/
	102	if (ret == LRU_REMOVED_RETRY)
	103	goto restart;
a38e4082 DC	104	break;
a38e4082 DC	105	case LRU_ROTATE:
3b1d58a4	106	list_move_tail(item, &nlru->list);
a38e4082 DC	107	break;
	108	case LRU_SKIP:
	109	break;
	110	case LRU_RETRY:
5cedf721 DC	111	/*
	112	* The lru lock has been dropped, our list traversal is
	113	* now invalid and so we have to restart from scratch.
	114	*/
449dd698	115	assert_spin_locked(&nlru->lock);
a38e4082 DC	116	goto restart;
	117	default:
	118	BUG();
	119	}
a38e4082	120	}
3b1d58a4 DC	121
	122	spin_unlock(&nlru->lock);
	123	return isolated;
	124	}
	125	EXPORT_SYMBOL_GPL(list_lru_walk_node);
	126
449dd698	127	int list_lru_init_key(struct list_lru lru, struct lock_class_key key)
a38e4082	128	{
3b1d58a4	129	int i;
5ca302c8 GC	130	size_t size = sizeof(lru->node) nr_node_ids;
	131
	132	lru->node = kzalloc(size, GFP_KERNEL);
	133	if (!lru->node)
	134	return -ENOMEM;
a38e4082	135
3b1d58a4	136	nodes_clear(lru->active_nodes);
5ca302c8	137	for (i = 0; i < nr_node_ids; i++) {
3b1d58a4	138	spin_lock_init(&lru->node[i].lock);
449dd698 JW	139	if (key)
449dd698 JW	140	lockdep_set_class(&lru->node[i].lock, key);
3b1d58a4 DC	141	INIT_LIST_HEAD(&lru->node[i].list);
	142	lru->node[i].nr_items = 0;
	143	}
a38e4082 DC	144	return 0;
a38e4082 DC	145	}
449dd698	146	EXPORT_SYMBOL_GPL(list_lru_init_key);
5ca302c8 GC	147
	148	void list_lru_destroy(struct list_lru *lru)
	149	{
	150	kfree(lru->node);
	151	}
	152	EXPORT_SYMBOL_GPL(list_lru_destroy);