list_lru.c revision 5cedf721a7cdb54e9222133516c916210d836470 
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>
9#include <linux/mm.h>
10#include <linux/list_lru.h>
11
12bool list_lru_add(struct list_lru *lru, struct list_head *item)
13{
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);
19	if (list_empty(item)) {
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);
24		return true;
25	}
26	spin_unlock(&nlru->lock);
27	return false;
28}
29EXPORT_SYMBOL_GPL(list_lru_add);
30
31bool list_lru_del(struct list_lru *lru, struct list_head *item)
32{
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);
37	if (!list_empty(item)) {
38		list_del_init(item);
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);
43		return true;
44	}
45	spin_unlock(&nlru->lock);
46	return false;
47}
48EXPORT_SYMBOL_GPL(list_lru_del);
49
50unsigned long list_lru_count(struct list_lru *lru)
51{
52	unsigned long count = 0;
53	int nid;
54
55	for_each_node_mask(nid, lru->active_nodes) {
56		struct list_lru_node *nlru = &lru->node[nid];
57
58		spin_lock(&nlru->lock);
59		WARN_ON_ONCE(nlru->nr_items < 0);
60		count += nlru->nr_items;
61		spin_unlock(&nlru->lock);
62	}
63
64	return count;
65}
66EXPORT_SYMBOL_GPL(list_lru_count);
67
68static unsigned long
69list_lru_walk_node(struct list_lru *lru, int nid, list_lru_walk_cb isolate,
70		   void *cb_arg, unsigned long *nr_to_walk)
71{
72
73	struct list_lru_node	*nlru = &lru->node[nid];
74	struct list_head *item, *n;
75	unsigned long isolated = 0;
76
77	spin_lock(&nlru->lock);
78restart:
79	list_for_each_safe(item, n, &nlru->list) {
80		enum lru_status ret;
81
82		/*
83		 * decrement nr_to_walk first so that we don't livelock if we
84		 * get stuck on large numbesr of LRU_RETRY items
85		 */
86		if (--(*nr_to_walk) == 0)
87			break;
88
89		ret = isolate(item, &nlru->lock, cb_arg);
90		switch (ret) {
91		case LRU_REMOVED:
92			if (--nlru->nr_items == 0)
93				node_clear(nid, lru->active_nodes);
94			WARN_ON_ONCE(nlru->nr_items < 0);
95			isolated++;
96			break;
97		case LRU_ROTATE:
98			list_move_tail(item, &nlru->list);
99			break;
100		case LRU_SKIP:
101			break;
102		case LRU_RETRY:
103			/*
104			 * The lru lock has been dropped, our list traversal is
105			 * now invalid and so we have to restart from scratch.
106			 */
107			goto restart;
108		default:
109			BUG();
110		}
111	}
112
113	spin_unlock(&nlru->lock);
114	return isolated;
115}
116EXPORT_SYMBOL_GPL(list_lru_walk_node);
117
118unsigned long list_lru_walk(struct list_lru *lru, list_lru_walk_cb isolate,
119			    void *cb_arg, unsigned long nr_to_walk)
120{
121	unsigned long isolated = 0;
122	int nid;
123
124	for_each_node_mask(nid, lru->active_nodes) {
125		isolated += list_lru_walk_node(lru, nid, isolate,
126					       cb_arg, &nr_to_walk);
127		if (nr_to_walk <= 0)
128			break;
129	}
130	return isolated;
131}
132EXPORT_SYMBOL_GPL(list_lru_walk);
133
134static unsigned long list_lru_dispose_all_node(struct list_lru *lru, int nid,
135					       list_lru_dispose_cb dispose)
136{
137	struct list_lru_node	*nlru = &lru->node[nid];
138	LIST_HEAD(dispose_list);
139	unsigned long disposed = 0;
140
141	spin_lock(&nlru->lock);
142	while (!list_empty(&nlru->list)) {
143		list_splice_init(&nlru->list, &dispose_list);
144		disposed += nlru->nr_items;
145		nlru->nr_items = 0;
146		node_clear(nid, lru->active_nodes);
147		spin_unlock(&nlru->lock);
148
149		dispose(&dispose_list);
150
151		spin_lock(&nlru->lock);
152	}
153	spin_unlock(&nlru->lock);
154	return disposed;
155}
156
157unsigned long list_lru_dispose_all(struct list_lru *lru,
158				   list_lru_dispose_cb dispose)
159{
160	unsigned long disposed;
161	unsigned long total = 0;
162	int nid;
163
164	do {
165		disposed = 0;
166		for_each_node_mask(nid, lru->active_nodes) {
167			disposed += list_lru_dispose_all_node(lru, nid,
168							      dispose);
169		}
170		total += disposed;
171	} while (disposed != 0);
172
173	return total;
174}
175
176int list_lru_init(struct list_lru *lru)
177{
178	int i;
179
180	nodes_clear(lru->active_nodes);
181	for (i = 0; i < MAX_NUMNODES; i++) {
182		spin_lock_init(&lru->node[i].lock);
183		INIT_LIST_HEAD(&lru->node[i].list);
184		lru->node[i].nr_items = 0;
185	}
186	return 0;
187}
188EXPORT_SYMBOL_GPL(list_lru_init);
189