]>
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; |
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)) { |
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; |
44 | } | |
3b1d58a4 | 45 | spin_unlock(&nlru->lock); |
a38e4082 DC |
46 | return false; |
47 | } | |
48 | EXPORT_SYMBOL_GPL(list_lru_del); | |
49 | ||
3b1d58a4 | 50 | unsigned long list_lru_count(struct list_lru *lru) |
a38e4082 | 51 | { |
3b1d58a4 DC |
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 | } | |
66 | EXPORT_SYMBOL_GPL(list_lru_count); | |
67 | ||
68 | static unsigned long | |
69 | list_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]; | |
a38e4082 | 74 | struct list_head *item, *n; |
3b1d58a4 | 75 | unsigned long isolated = 0; |
a38e4082 | 76 | |
3b1d58a4 | 77 | spin_lock(&nlru->lock); |
a38e4082 | 78 | restart: |
3b1d58a4 | 79 | list_for_each_safe(item, n, &nlru->list) { |
a38e4082 | 80 | enum lru_status ret; |
5cedf721 DC |
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 | ||
3b1d58a4 | 89 | ret = isolate(item, &nlru->lock, cb_arg); |
a38e4082 DC |
90 | switch (ret) { |
91 | case LRU_REMOVED: | |
3b1d58a4 DC |
92 | if (--nlru->nr_items == 0) |
93 | node_clear(nid, lru->active_nodes); | |
94 | WARN_ON_ONCE(nlru->nr_items < 0); | |
95 | isolated++; | |
a38e4082 DC |
96 | break; |
97 | case LRU_ROTATE: | |
3b1d58a4 | 98 | list_move_tail(item, &nlru->list); |
a38e4082 DC |
99 | break; |
100 | case LRU_SKIP: | |
101 | break; | |
102 | case LRU_RETRY: | |
5cedf721 DC |
103 | /* |
104 | * The lru lock has been dropped, our list traversal is | |
105 | * now invalid and so we have to restart from scratch. | |
106 | */ | |
a38e4082 DC |
107 | goto restart; |
108 | default: | |
109 | BUG(); | |
110 | } | |
a38e4082 | 111 | } |
3b1d58a4 DC |
112 | |
113 | spin_unlock(&nlru->lock); | |
114 | return isolated; | |
115 | } | |
116 | EXPORT_SYMBOL_GPL(list_lru_walk_node); | |
117 | ||
118 | unsigned 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; | |
a38e4082 DC |
131 | } |
132 | EXPORT_SYMBOL_GPL(list_lru_walk); | |
133 | ||
3b1d58a4 DC |
134 | static unsigned long list_lru_dispose_all_node(struct list_lru *lru, int nid, |
135 | list_lru_dispose_cb dispose) | |
a38e4082 | 136 | { |
3b1d58a4 | 137 | struct list_lru_node *nlru = &lru->node[nid]; |
a38e4082 | 138 | LIST_HEAD(dispose_list); |
3b1d58a4 | 139 | unsigned long disposed = 0; |
a38e4082 | 140 | |
3b1d58a4 DC |
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); | |
a38e4082 DC |
148 | |
149 | dispose(&dispose_list); | |
150 | ||
3b1d58a4 | 151 | spin_lock(&nlru->lock); |
a38e4082 | 152 | } |
3b1d58a4 | 153 | spin_unlock(&nlru->lock); |
a38e4082 DC |
154 | return disposed; |
155 | } | |
156 | ||
3b1d58a4 DC |
157 | unsigned 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 | ||
a38e4082 DC |
176 | int list_lru_init(struct list_lru *lru) |
177 | { | |
3b1d58a4 | 178 | int i; |
a38e4082 | 179 | |
3b1d58a4 DC |
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 | } | |
a38e4082 DC |
186 | return 0; |
187 | } | |
188 | EXPORT_SYMBOL_GPL(list_lru_init); |