[linux-2.6-block.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>

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) == 0)
			break;

		ret = isolate(item, &nlru->lock, cb_arg);
		switch (ret) {
		case LRU_REMOVED:
			if (--nlru->nr_items == 0)
				node_clear(nid, lru->active_nodes);
			WARN_ON_ONCE(nlru->nr_items < 0);
			isolated++;
			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.
			 */
			goto restart;
		default:
			BUG();
		}
	}

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

int list_lru_init(struct list_lru *lru)
{
	int i;

	nodes_clear(lru->active_nodes);
	for (i = 0; i < MAX_NUMNODES; i++) {
		spin_lock_init(&lru->node[i].lock);
		INIT_LIST_HEAD(&lru->node[i].list);
		lru->node[i].nr_items = 0;
	}
	return 0;
}
EXPORT_SYMBOL_GPL(list_lru_init);
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 DC	10	#include <linux/list_lru.h>
	11
	12	bool list_lru_add(struct list_lru lru, struct list_head item)
	13	{
3b1d58a4 DC	14	int nid = page_to_nid(virt_to_page(item));
	15	struct list_lru_node *nlru = &lru->node[nid];
	16
	17	spin_lock(&nlru->lock);
	18	WARN_ON_ONCE(nlru->nr_items < 0);
a38e4082	19	if (list_empty(item)) {
3b1d58a4 DC	20	list_add_tail(item, &nlru->list);
	21	if (nlru->nr_items++ == 0)
	22	node_set(nid, lru->active_nodes);
	23	spin_unlock(&nlru->lock);
a38e4082 DC	24	return true;
a38e4082 DC	25	}
3b1d58a4	26	spin_unlock(&nlru->lock);
a38e4082 DC	27	return false;
	28	}
	29	EXPORT_SYMBOL_GPL(list_lru_add);
	30
	31	bool list_lru_del(struct list_lru lru, struct list_head item)
	32	{
3b1d58a4 DC	33	int nid = page_to_nid(virt_to_page(item));
	34	struct list_lru_node *nlru = &lru->node[nid];
	35
	36	spin_lock(&nlru->lock);
a38e4082 DC	37	if (!list_empty(item)) {
a38e4082 DC	38	list_del_init(item);
3b1d58a4 DC	39	if (--nlru->nr_items == 0)
	40	node_clear(nid, lru->active_nodes);
	41	WARN_ON_ONCE(nlru->nr_items < 0);
	42	spin_unlock(&nlru->lock);
a38e4082 DC	43	return true;
a38e4082 DC	44	}
3b1d58a4	45	spin_unlock(&nlru->lock);
a38e4082 DC	46	return false;
	47	}
	48	EXPORT_SYMBOL_GPL(list_lru_del);
	49
6a4f496f GC	50	unsigned long
6a4f496f GC	51	list_lru_count_node(struct list_lru *lru, int nid)
a38e4082	52	{
3b1d58a4	53	unsigned long count = 0;
6a4f496f	54	struct list_lru_node *nlru = &lru->node[nid];
3b1d58a4	55
6a4f496f GC	56	spin_lock(&nlru->lock);
	57	WARN_ON_ONCE(nlru->nr_items < 0);
	58	count += nlru->nr_items;
	59	spin_unlock(&nlru->lock);
3b1d58a4 DC	60
	61	return count;
	62	}
6a4f496f	63	EXPORT_SYMBOL_GPL(list_lru_count_node);
3b1d58a4	64
6a4f496f	65	unsigned long
3b1d58a4 DC	66	list_lru_walk_node(struct list_lru *lru, int nid, list_lru_walk_cb isolate,
	67	void cb_arg, unsigned long nr_to_walk)
	68	{
	69
	70	struct list_lru_node *nlru = &lru->node[nid];
a38e4082	71	struct list_head item, n;
3b1d58a4	72	unsigned long isolated = 0;
a38e4082	73
3b1d58a4	74	spin_lock(&nlru->lock);
a38e4082	75	restart:
3b1d58a4	76	list_for_each_safe(item, n, &nlru->list) {
a38e4082	77	enum lru_status ret;
5cedf721 DC	78
	79	/*
	80	* decrement nr_to_walk first so that we don't livelock if we
	81	* get stuck on large numbesr of LRU_RETRY items
	82	*/
	83	if (--(*nr_to_walk) == 0)
	84	break;
	85
3b1d58a4	86	ret = isolate(item, &nlru->lock, cb_arg);
a38e4082 DC	87	switch (ret) {
a38e4082 DC	88	case LRU_REMOVED:
3b1d58a4 DC	89	if (--nlru->nr_items == 0)
	90	node_clear(nid, lru->active_nodes);
	91	WARN_ON_ONCE(nlru->nr_items < 0);
	92	isolated++;
a38e4082 DC	93	break;
a38e4082 DC	94	case LRU_ROTATE:
3b1d58a4	95	list_move_tail(item, &nlru->list);
a38e4082 DC	96	break;
	97	case LRU_SKIP:
	98	break;
	99	case LRU_RETRY:
5cedf721 DC	100	/*
	101	* The lru lock has been dropped, our list traversal is
	102	* now invalid and so we have to restart from scratch.
	103	*/
a38e4082 DC	104	goto restart;
	105	default:
	106	BUG();
	107	}
a38e4082	108	}
3b1d58a4 DC	109
	110	spin_unlock(&nlru->lock);
	111	return isolated;
	112	}
	113	EXPORT_SYMBOL_GPL(list_lru_walk_node);
	114
a38e4082 DC	115	int list_lru_init(struct list_lru *lru)
a38e4082 DC	116	{
3b1d58a4	117	int i;
a38e4082	118
3b1d58a4 DC	119	nodes_clear(lru->active_nodes);
	120	for (i = 0; i < MAX_NUMNODES; i++) {
	121	spin_lock_init(&lru->node[i].lock);
	122	INIT_LIST_HEAD(&lru->node[i].list);
	123	lru->node[i].nr_items = 0;
	124	}
a38e4082 DC	125	return 0;
	126	}
	127	EXPORT_SYMBOL_GPL(list_lru_init);