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 | 10 | #include <linux/list_lru.h> |
5ca302c8 | 11 | #include <linux/slab.h> |
a38e4082 DC |
12 | |
13 | bool list_lru_add(struct list_lru *lru, struct list_head *item) | |
14 | { | |
3b1d58a4 DC |
15 | int nid = page_to_nid(virt_to_page(item)); |
16 | struct list_lru_node *nlru = &lru->node[nid]; | |
17 | ||
18 | spin_lock(&nlru->lock); | |
19 | WARN_ON_ONCE(nlru->nr_items < 0); | |
a38e4082 | 20 | if (list_empty(item)) { |
3b1d58a4 | 21 | list_add_tail(item, &nlru->list); |
ff0b67ef | 22 | nlru->nr_items++; |
3b1d58a4 | 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); | |
ff0b67ef | 39 | nlru->nr_items--; |
3b1d58a4 DC |
40 | WARN_ON_ONCE(nlru->nr_items < 0); |
41 | spin_unlock(&nlru->lock); | |
a38e4082 DC |
42 | return true; |
43 | } | |
3b1d58a4 | 44 | spin_unlock(&nlru->lock); |
a38e4082 DC |
45 | return false; |
46 | } | |
47 | EXPORT_SYMBOL_GPL(list_lru_del); | |
48 | ||
6a4f496f GC |
49 | unsigned long |
50 | list_lru_count_node(struct list_lru *lru, int nid) | |
a38e4082 | 51 | { |
3b1d58a4 | 52 | unsigned long count = 0; |
6a4f496f | 53 | struct list_lru_node *nlru = &lru->node[nid]; |
3b1d58a4 | 54 | |
6a4f496f GC |
55 | spin_lock(&nlru->lock); |
56 | WARN_ON_ONCE(nlru->nr_items < 0); | |
57 | count += nlru->nr_items; | |
58 | spin_unlock(&nlru->lock); | |
3b1d58a4 DC |
59 | |
60 | return count; | |
61 | } | |
6a4f496f | 62 | EXPORT_SYMBOL_GPL(list_lru_count_node); |
3b1d58a4 | 63 | |
6a4f496f | 64 | unsigned long |
3b1d58a4 DC |
65 | list_lru_walk_node(struct list_lru *lru, int nid, list_lru_walk_cb isolate, |
66 | void *cb_arg, unsigned long *nr_to_walk) | |
67 | { | |
68 | ||
69 | struct list_lru_node *nlru = &lru->node[nid]; | |
a38e4082 | 70 | struct list_head *item, *n; |
3b1d58a4 | 71 | unsigned long isolated = 0; |
a38e4082 | 72 | |
3b1d58a4 | 73 | spin_lock(&nlru->lock); |
a38e4082 | 74 | restart: |
3b1d58a4 | 75 | list_for_each_safe(item, n, &nlru->list) { |
a38e4082 | 76 | enum lru_status ret; |
5cedf721 DC |
77 | |
78 | /* | |
79 | * decrement nr_to_walk first so that we don't livelock if we | |
80 | * get stuck on large numbesr of LRU_RETRY items | |
81 | */ | |
c56b097a | 82 | if (!*nr_to_walk) |
5cedf721 | 83 | break; |
c56b097a | 84 | --*nr_to_walk; |
5cedf721 | 85 | |
3b1d58a4 | 86 | ret = isolate(item, &nlru->lock, cb_arg); |
a38e4082 | 87 | switch (ret) { |
449dd698 JW |
88 | case LRU_REMOVED_RETRY: |
89 | assert_spin_locked(&nlru->lock); | |
a38e4082 | 90 | case LRU_REMOVED: |
ff0b67ef | 91 | nlru->nr_items--; |
3b1d58a4 DC |
92 | WARN_ON_ONCE(nlru->nr_items < 0); |
93 | isolated++; | |
449dd698 JW |
94 | /* |
95 | * If the lru lock has been dropped, our list | |
96 | * traversal is now invalid and so we have to | |
97 | * restart from scratch. | |
98 | */ | |
99 | if (ret == LRU_REMOVED_RETRY) | |
100 | goto restart; | |
a38e4082 DC |
101 | break; |
102 | case LRU_ROTATE: | |
3b1d58a4 | 103 | list_move_tail(item, &nlru->list); |
a38e4082 DC |
104 | break; |
105 | case LRU_SKIP: | |
106 | break; | |
107 | case LRU_RETRY: | |
5cedf721 DC |
108 | /* |
109 | * The lru lock has been dropped, our list traversal is | |
110 | * now invalid and so we have to restart from scratch. | |
111 | */ | |
449dd698 | 112 | assert_spin_locked(&nlru->lock); |
a38e4082 DC |
113 | goto restart; |
114 | default: | |
115 | BUG(); | |
116 | } | |
a38e4082 | 117 | } |
3b1d58a4 DC |
118 | |
119 | spin_unlock(&nlru->lock); | |
120 | return isolated; | |
121 | } | |
122 | EXPORT_SYMBOL_GPL(list_lru_walk_node); | |
123 | ||
449dd698 | 124 | int list_lru_init_key(struct list_lru *lru, struct lock_class_key *key) |
a38e4082 | 125 | { |
3b1d58a4 | 126 | int i; |
5ca302c8 GC |
127 | size_t size = sizeof(*lru->node) * nr_node_ids; |
128 | ||
129 | lru->node = kzalloc(size, GFP_KERNEL); | |
130 | if (!lru->node) | |
131 | return -ENOMEM; | |
a38e4082 | 132 | |
5ca302c8 | 133 | for (i = 0; i < nr_node_ids; i++) { |
3b1d58a4 | 134 | spin_lock_init(&lru->node[i].lock); |
449dd698 JW |
135 | if (key) |
136 | lockdep_set_class(&lru->node[i].lock, key); | |
3b1d58a4 DC |
137 | INIT_LIST_HEAD(&lru->node[i].list); |
138 | lru->node[i].nr_items = 0; | |
139 | } | |
a38e4082 DC |
140 | return 0; |
141 | } | |
449dd698 | 142 | EXPORT_SYMBOL_GPL(list_lru_init_key); |
5ca302c8 GC |
143 | |
144 | void list_lru_destroy(struct list_lru *lru) | |
145 | { | |
146 | kfree(lru->node); | |
147 | } | |
148 | EXPORT_SYMBOL_GPL(list_lru_destroy); |