list_lru.c 3.1 KB
Newer Older
D
Dave Chinner 已提交
1 2 3 4 5 6 7 8
/*
 * 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>
9
#include <linux/mm.h>
D
Dave Chinner 已提交
10
#include <linux/list_lru.h>
11
#include <linux/slab.h>
D
Dave Chinner 已提交
12 13 14

bool list_lru_add(struct list_lru *lru, struct list_head *item)
{
15 16 17 18 19
	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);
D
Dave Chinner 已提交
20
	if (list_empty(item)) {
21 22 23 24
		list_add_tail(item, &nlru->list);
		if (nlru->nr_items++ == 0)
			node_set(nid, lru->active_nodes);
		spin_unlock(&nlru->lock);
D
Dave Chinner 已提交
25 26
		return true;
	}
27
	spin_unlock(&nlru->lock);
D
Dave Chinner 已提交
28 29 30 31 32 33
	return false;
}
EXPORT_SYMBOL_GPL(list_lru_add);

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

	spin_lock(&nlru->lock);
D
Dave Chinner 已提交
38 39
	if (!list_empty(item)) {
		list_del_init(item);
40 41 42 43
		if (--nlru->nr_items == 0)
			node_clear(nid, lru->active_nodes);
		WARN_ON_ONCE(nlru->nr_items < 0);
		spin_unlock(&nlru->lock);
D
Dave Chinner 已提交
44 45
		return true;
	}
46
	spin_unlock(&nlru->lock);
D
Dave Chinner 已提交
47 48 49 50
	return false;
}
EXPORT_SYMBOL_GPL(list_lru_del);

G
Glauber Costa 已提交
51 52
unsigned long
list_lru_count_node(struct list_lru *lru, int nid)
D
Dave Chinner 已提交
53
{
54
	unsigned long count = 0;
G
Glauber Costa 已提交
55
	struct list_lru_node *nlru = &lru->node[nid];
56

G
Glauber Costa 已提交
57 58 59 60
	spin_lock(&nlru->lock);
	WARN_ON_ONCE(nlru->nr_items < 0);
	count += nlru->nr_items;
	spin_unlock(&nlru->lock);
61 62 63

	return count;
}
G
Glauber Costa 已提交
64
EXPORT_SYMBOL_GPL(list_lru_count_node);
65

G
Glauber Costa 已提交
66
unsigned long
67 68 69 70 71
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];
D
Dave Chinner 已提交
72
	struct list_head *item, *n;
73
	unsigned long isolated = 0;
D
Dave Chinner 已提交
74

75
	spin_lock(&nlru->lock);
D
Dave Chinner 已提交
76
restart:
77
	list_for_each_safe(item, n, &nlru->list) {
D
Dave Chinner 已提交
78
		enum lru_status ret;
79 80 81 82 83

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

88
		ret = isolate(item, &nlru->lock, cb_arg);
D
Dave Chinner 已提交
89 90
		switch (ret) {
		case LRU_REMOVED:
91 92 93 94
			if (--nlru->nr_items == 0)
				node_clear(nid, lru->active_nodes);
			WARN_ON_ONCE(nlru->nr_items < 0);
			isolated++;
D
Dave Chinner 已提交
95 96
			break;
		case LRU_ROTATE:
97
			list_move_tail(item, &nlru->list);
D
Dave Chinner 已提交
98 99 100 101
			break;
		case LRU_SKIP:
			break;
		case LRU_RETRY:
102 103 104 105
			/*
			 * The lru lock has been dropped, our list traversal is
			 * now invalid and so we have to restart from scratch.
			 */
D
Dave Chinner 已提交
106 107 108 109 110
			goto restart;
		default:
			BUG();
		}
	}
111 112 113 114 115 116

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

D
Dave Chinner 已提交
117 118
int list_lru_init(struct list_lru *lru)
{
119
	int i;
120 121 122 123 124
	size_t size = sizeof(*lru->node) * nr_node_ids;

	lru->node = kzalloc(size, GFP_KERNEL);
	if (!lru->node)
		return -ENOMEM;
D
Dave Chinner 已提交
125

126
	nodes_clear(lru->active_nodes);
127
	for (i = 0; i < nr_node_ids; i++) {
128 129 130 131
		spin_lock_init(&lru->node[i].lock);
		INIT_LIST_HEAD(&lru->node[i].list);
		lru->node[i].nr_items = 0;
	}
D
Dave Chinner 已提交
132 133 134
	return 0;
}
EXPORT_SYMBOL_GPL(list_lru_init);
135 136 137 138 139 140

void list_lru_destroy(struct list_lru *lru)
{
	kfree(lru->node);
}
EXPORT_SYMBOL_GPL(list_lru_destroy);