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 DC |
76 | /* |
77 | * If we don't keep state of at which pass we are, we can loop at | |
78 | * LRU_RETRY, since we have no guarantees that the caller will be able | |
79 | * to do something other than retry on the next pass. We handle this by | |
80 | * allowing at most one retry per object. This should not be altered | |
81 | * by any condition other than LRU_RETRY. | |
82 | */ | |
83 | bool first_pass = true; | |
84 | ||
3b1d58a4 | 85 | spin_lock(&nlru->lock); |
a38e4082 | 86 | restart: |
3b1d58a4 | 87 | list_for_each_safe(item, n, &nlru->list) { |
a38e4082 | 88 | enum lru_status ret; |
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: | |
103 | if (!first_pass) { | |
104 | first_pass = true; | |
105 | break; | |
106 | } | |
107 | first_pass = false; | |
108 | goto restart; | |
109 | default: | |
110 | BUG(); | |
111 | } | |
112 | ||
3b1d58a4 | 113 | if ((*nr_to_walk)-- == 0) |
a38e4082 DC |
114 | break; |
115 | ||
116 | } | |
3b1d58a4 DC |
117 | |
118 | spin_unlock(&nlru->lock); | |
119 | return isolated; | |
120 | } | |
121 | EXPORT_SYMBOL_GPL(list_lru_walk_node); | |
122 | ||
123 | unsigned long list_lru_walk(struct list_lru *lru, list_lru_walk_cb isolate, | |
124 | void *cb_arg, unsigned long nr_to_walk) | |
125 | { | |
126 | unsigned long isolated = 0; | |
127 | int nid; | |
128 | ||
129 | for_each_node_mask(nid, lru->active_nodes) { | |
130 | isolated += list_lru_walk_node(lru, nid, isolate, | |
131 | cb_arg, &nr_to_walk); | |
132 | if (nr_to_walk <= 0) | |
133 | break; | |
134 | } | |
135 | return isolated; | |
a38e4082 DC |
136 | } |
137 | EXPORT_SYMBOL_GPL(list_lru_walk); | |
138 | ||
3b1d58a4 DC |
139 | static unsigned long list_lru_dispose_all_node(struct list_lru *lru, int nid, |
140 | list_lru_dispose_cb dispose) | |
a38e4082 | 141 | { |
3b1d58a4 | 142 | struct list_lru_node *nlru = &lru->node[nid]; |
a38e4082 | 143 | LIST_HEAD(dispose_list); |
3b1d58a4 | 144 | unsigned long disposed = 0; |
a38e4082 | 145 | |
3b1d58a4 DC |
146 | spin_lock(&nlru->lock); |
147 | while (!list_empty(&nlru->list)) { | |
148 | list_splice_init(&nlru->list, &dispose_list); | |
149 | disposed += nlru->nr_items; | |
150 | nlru->nr_items = 0; | |
151 | node_clear(nid, lru->active_nodes); | |
152 | spin_unlock(&nlru->lock); | |
a38e4082 DC |
153 | |
154 | dispose(&dispose_list); | |
155 | ||
3b1d58a4 | 156 | spin_lock(&nlru->lock); |
a38e4082 | 157 | } |
3b1d58a4 | 158 | spin_unlock(&nlru->lock); |
a38e4082 DC |
159 | return disposed; |
160 | } | |
161 | ||
3b1d58a4 DC |
162 | unsigned long list_lru_dispose_all(struct list_lru *lru, |
163 | list_lru_dispose_cb dispose) | |
164 | { | |
165 | unsigned long disposed; | |
166 | unsigned long total = 0; | |
167 | int nid; | |
168 | ||
169 | do { | |
170 | disposed = 0; | |
171 | for_each_node_mask(nid, lru->active_nodes) { | |
172 | disposed += list_lru_dispose_all_node(lru, nid, | |
173 | dispose); | |
174 | } | |
175 | total += disposed; | |
176 | } while (disposed != 0); | |
177 | ||
178 | return total; | |
179 | } | |
180 | ||
a38e4082 DC |
181 | int list_lru_init(struct list_lru *lru) |
182 | { | |
3b1d58a4 | 183 | int i; |
a38e4082 | 184 | |
3b1d58a4 DC |
185 | nodes_clear(lru->active_nodes); |
186 | for (i = 0; i < MAX_NUMNODES; i++) { | |
187 | spin_lock_init(&lru->node[i].lock); | |
188 | INIT_LIST_HEAD(&lru->node[i].list); | |
189 | lru->node[i].nr_items = 0; | |
190 | } | |
a38e4082 DC |
191 | return 0; |
192 | } | |
193 | EXPORT_SYMBOL_GPL(list_lru_init); |